[C++] 백준 11048번 이동하기

처음에 그래프 탐색 문제인 줄 알았던 문제.

알고보니 다이나믹 프로그래밍 문제였다.

DFS로 구현하려고 하니까 시간 초과가 났다.

생각해 보면 최대 정점의 개수가 1000 x 1000 해서 1,000,000개가 되는데

각 점마다 3번의 메서드를 호출하게 된다.

이렇게 되면 3^1000000이므로 시간초과가 날 수 밖에 없다.

DP인 것을 알고나면 쉽게 해결할 수가 있다.

 

문제풀이

DP의 관점에서, 각 칸의 도달할 수 있는 경우는 다음 세가지이다.

y, x의 좌표로 부른다고 할 때,

1. (y - 1, x)에서 (y, x) : 이전 칸이 위에서 아래로 이동한 경우 (r + 1, c) 
2. (y, x - 1)에서 (y, x) : 이전 칸이 좌측에서 우측으로 이동한 경우 (r, c + 1)
3. (y - 1, x - 1)에서 (y, x) : 이전 칸에서 우하 대각선으로 이동한 경우(r + 1, c + 1)

그리고 각 미로를 벗어나는 경우는 없다.

 

미로의 각 칸마다 사탕의 개수를 나타내는 배열을 maze,

각 칸에 도달했을 때의 최대 사탕의 개수를 나타내는 배열을 maxCandy,

max(A, B, C)를 최대값을 반환하는 메서드라고 부르기로 한다면

maxCandy[1][1] = maze[1][1]	maxCandy[1][2] = maxCandy[1][1] + maze[1][2]	maxCandy[1][3] = maxCandy[1][2] + maze[1][3]
maxCandy[2][1] = maxCandy[1][1] + maze[2][1]	maxCandy[2][2] = max(maxCandy[1][1],          maxCandy[1][2],          maxCandy[2][1])         +maze[2][2]	maxCandy[2][3] = max(maxCandy[1][2],          maxCandy[1][3],          maxCandy[2][2])         +maze[2][3]

위와같이 올 수 있는 경우들만 고려해서 DP값을 업데이트 해나가며 문제를 해결하면 된다.

 

사용한 STL과 변수

max() 메서드를 사용하기위해 algorithm STL을 사용했다.

미로의 높이와 너비 변수를 만들었고 미로에서 각 칸의 사탕의 개수를 담는 maze배열과

각 칸에 도달했을 때의 최대값을 기록하는 maxCandy 배열을 만들었다.

 

maxCandy의 사이즈가 최대 너비와 최대 높이인 1,000에서 1을 더했는데 

이는 위와같은 로직으로 짤 경우 마지막 행, 마지막 열에서 반복문을 벗어나는 것을 방지하기

위해서 위처럼 사이즈를 1을 더 주었다.

000000000 012345670 012345670 000000000

1~7까지 2x7 미로가 있다면 위와같은 그림이 될 것이다.

 

메인함수

미로의 높이와 너비를 입력받고 각 칸에서 몇 개의 사탕이 있는지 입력받는다.

 

그리고 반복문을 돌면서 위에서 설명했던 로직 그대로 각 칸에서 최대값을 업데이트 시킨다.

 

마지막으로 문제에서 원하는 M, N에 도달했을 때의 최대값을 출력한다.

 

당연히 DFS, BFS 문제일거라고 생각해서 시간도 고려하지 않았다.

결국 알고리즘 분류를 보고나서야 DP문제이고, 시간도 당연히 초과될 수 밖에 없다는 것을 알았다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인이 가능하다.