[BOJ] 2740. 행렬 곱셈 (Java)

문제 링크 / level: Bronze I

https://www.acmicpc.net/problem/2740

2740번: 행렬 곱셈

 

 

내가 생각한 풀이

고등학교, 대학교 때 많이 계산했던 행렬의 곱셈 연산에 관한 문제였다.

그런데 간단한 규칙에 비해 코드로 구현하는데 생각보다 어려움이 좀 있었다.🤔💦

 

일단 행렬의 곱셈을 위한 조건을 알아보자.

첫 번째 행렬(first)의 크기: N * M

두 번째 행렬(second)의 크기: M * K

 

<수학적으로 알아야하는 것>

1. 이 중 M의 값이 반드시 같아야하는데 문제에서 입력값을 둘 다 M으로 주기 때문에 신경 쓸 필요 없다.

2. 행렬의 곱셈 연산 후 결과값으로 나오는 행렬의 크기: N * K

3. 행렬의 곱셈 공식: result(i,j)의 값을 구하고 싶다면 first의 i행의 성분과 second의 j열의 성분을 곱한 것들의 합이다.

행렬의 곱셈 연산 결과는 대충 이런 느낌이다. (왼쪽은 과정을 식으로 풀어쓴 것, 오른쪽은 좌표)

이 중 이해가 잘 가지 않는 부분이 있다면 수학의 정석,, 아니면 수학의 바이블,, 혹은 인터넷에 검색해보시는걸 추천합니다.

 

---

 

아무튼 행렬의 곱셈 연산 과정을 쭉 훑어보면

- first[][]의 첫 번째 인덱스가 가장 바깥에 있는 for문을 돌아야 한다. (N만큼 반복한 후 1 증가)
- second[][]의 두 번째 인덱스는 result 배열의 열과 같은 값으로 고정.
- first[][]의 두 번째 인덱스와 second[][]의 첫 번째 인덱스의 값은 같다. (0부터 M-1까지 계속 반복)

 

이 로직을 적절히 코드로 구현하는 것이 바로 이 문제의 핵심이다.

이제 코드로 구현해보자!!

// 핵심 코드
// 행렬의 곱셈 연산 (i행의 성분 * j열의 성분을 곱한 것들의 합)
for (int i = 0; i < N; i++) { // 3
	for (int j = 0; j < K; j++) { // 3
		for (int k = 0; k < M; k++) { // 2
			result[i][j] += first[i][k] * second[k][j];
		}
	}
}

머리가 아파와서 이런 저런 코드를 좀 참고하다가 결과적으로 구현한 내 코드는 이러했다. (참고로 다시 한 번 이야기하자면 result는 결과값을 저장할 행렬(이라 쓰고 이차원배열이라고 읽는다.)이고, first는 첫 번째 행렬, second는 두 번째 행렬이다.)

 

3중 for문과 각 이차원배열들의 인덱스를 적절하게 잘 정해주어야 행렬의 곱셈을 구현할 수 있는데, 생각보다 머릿속으로만 돌려보는게 굉장히 힘든 작업이었다. 어떤건 고정되어야 하고, 어떤건 요만큼 돈 다음에 1 증가해야하고, 어떤건 저만큼 돈 다음에 다시 0으로 돌아와서 그 작업을 계속 반복해야하고... (나만 복잡한거니?😂)

그래서 3, 3, 2라고 적혀있는 주석은 백준 홈페이지에 문제의 예제로 주어진 값을 적어둔 것이다. 3중 for문으로 행렬 3개를 커버하려니 좀 헷갈려서...^_^

 

아무튼 위 코드를 한줄씩 차근차근 돌려보면

요런 식으로 코드가 작동한다는 것을 알 수 있다.

이렇게 행렬의 곱셈 연산이 잘 작동한다는 것을 알 수 있다.

 

전체 코드에서 가장 핵심이 되는 아무래도 이 부분.

result[i][j] += first[i][k] * second[k][j];

N * M 사이즈의 행렬과 M * K 사이즈의 행렬을 곱해서 N * K 사이즈의 행렬이 결과값으로 나온다.

따라서 result의 i와 j는 first의 i와 같고, second의 j와 같도록 맞춰주면 된다.

그리고 first의 M과 second M은 같이 움직여야하는 운명 공동체 같은 느낌이므로 둘 다 k로 맞춰주면 된다.

 

구현하기까지는 생각보다 머리가 아팠지만, 막상 구현을 완료한 후에 다시 보면 의외로 간단한 듯한 행렬의 곱셈 연산이었다.😂

 

성공!

 

어떻게 보면 이 행렬 곱셈 문제가 진정한 의미의 구현 문제였던 것 같은데, 생각보다 애를 많이 먹어서 속상하기도 했다. 흙흙,,😔

그래도 차근차근 하다보면 어떻게든 완성할 수 있는 것 또한 구현문제겠지... 기죽지 말고 파이팅!!👊🔥

 

 

 

💌 전체 코드 보기:

https://github.com/psS2mj/Problem_Solving_BOJ_by_JAVA/blob/master/Bronze/Main_2740_%ED%96%89%EB%A0%AC%EA%B3%B1%EC%85%88.java

psS2mj/Problem_Solving_BOJ_by_JAVA