서론
요즘 꾸준히 취업 준비를 하던 중이라, 매일 코딩 테스트를 하고 있다.
하루하루 일정을 꽉 채우느라 블로그에 신경을 못 썼던 것 같아 오랜만에 오늘 푼 알고리즘을 포스팅 할까 한다.
사실 여태 한 코테 모두 노션에 문제와 코드, 요약한 내용이 정리되어 있지만 블로그에 따로 풀이를 하듯 적는 것도 좋을 것 같고.
문제
문제는 위와 같고, 내리막 길만을 선택해서 목적지에 도달하는 경우의 수를 출력하면 되는 문제다.
모든 경우의 수를 찾아야 하니 알고리즘은 당연히 DFS를 생각했고,
다시 되돌아 가기 위해 백 트래킹을 적용시켰다.
결과는...
처참했다.
시간 초과 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M, CNT;
static int[] dx = {0, 0, 1, -1};
static int[] dy = {1, -1, 0, 0};
static int[][] map;
static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
visited = new boolean[N][M];
for(int i = 0; i < N; i++){
st = new StringTokenizer(br.readLine());
for(int j = 0; j < M; j++){
map[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0,0);
System.out.println(CNT);
}
public static void dfs(int x, int y){
visited[x][y] = true;
if(x == N-1 && y == M-1){
CNT++;
return;
}
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny]){
if(map[nx][ny] < map[x][y]){
visited[nx][ny] = true;
dfs(nx, ny);
visited[nx][ny] = false;
}
}
}
}
}위의 코드가 초기의 코드였는데 아무래도 시간 초과가 날 수밖에 없겠다, 싶어서 가지치기까지 모두 섞어 작성해 봤지만, 여전히 시간 초과가 발생했다.
조금 더 고민하다 든 생각이 하나 있었는데,
이럴 때 쓰라고 만든 게 Dynamic Programming 기법이다.
저번주 내내 DP 문제만 풀었더니 완전 탐색 코드의 감을 잃을까 봐 고른 문제였는데 결국 얘도 DP로 해결했다.
최종 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[] dx = {0, 0, 1, -1};
static int[] dy = {1, -1, 0, 0};
static int[][] map, dp;
static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
dp = new int[N + 1][M + 1];
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
dp[N - 1][M - 1] = 1;
System.out.println(dfs(0, 0));
}
public static int dfs(int x, int y) {
if (visited[x][y]) return dp[x][y];
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < M && map[nx][ny] < map[x][y])
dp[x][y] += dfs(nx, ny);
}
return dp[x][y];
}
}이러나 저러나 핵심 아이디어는 아래와 같다.
- 한 번 방문한 곳은 다시 방문하지 않기
- 최종 목적지의 DP 값은 미리 1로 설정하여 최종 목적지에 도착했을 시 경우의 수를 +1로 만들기
시간 초과를 없애기 위해 한 번 구한 경우의 수는 저장했다 꺼내 쓰는 방식으로 바꿔야 했고, 매번 dfs가 실행될 때마다 x, y가 최종 목적지와 일치하는지 확인하는게 번거로워 미리 dp[N-1][M-1]에 1을 설정했다.
여섯 번의 시도만에 성공했다.
또, DP로 바꾸고 나서도 계속 시간 초과가 났었다.
DP를 쓰는데 시간 초과가 난다면 내가 코드를 아주 단단히 잘못 적고 있구나 싶어서 평소에 쓰던 DFS랑 구조를 좀 다르게 바꿨다.
원래는 DFS에 들어오자마자 visited 배열을 true로 할당하는데, 이건 DP를 활용한 DFS이므로 탐색을 시작하기 전에 방문 여부를 먼저 확인한다.
만약 visited가 true라면, 얘는 이미 본인 위치에서 목적지까지 가는 경우의 수가 구해져 있는 거라 DP 값을 가지고 있을 수밖에 없다.
그래서 바로 dp[x][y]를 리턴해준다.
for문 안에서 탐색하는 코드는 별반 다를 게 없는데, 하나 다른 거라면 dfs 값을 dp에 할당해주는 것 정도다.
내 코드에서 dp[x][y]가 뜻하는 건 x행 y열에서 목적지까지 갈 수 있는 경우의 수다.
알고리즘 흐름도는 아래와 같다!
결론
매번 만만한 골드 4, 5 문제만 찾아 풀다가 이대로는 성장할 수 없으니 오랜만에 골드 3 문제를 풀어봤다.
요즈음 들어 느끼는 건데, 작년부터 꾸준히 코테를 풀었던 효과가 슬슬 나타나는 것 같다.
코테를 처음 시작할 때만 해도 어떤 알고리즘을 써야 할지 모르고, 실버 문제도 어려워서 끙끙댔는데..이제는 골드 문제도 나름 할만 한 것 같다.
앞으로도 지금처럼 쭉 성장할 수 있었으면 한다.
