[알고리즘] 등굣길 (프로그래머스 Level3)

코딩테스트 연습 - 등굣길

 문제 그림만 봐도 느껴지겠지만 탐색 문제이다. 다만 문제에서 최단 경로라고 언급을 했으니 BFS를 이용하기로 했다.

하지만 Level3 문제답게 단순한 BFS 문제는 아니다. 단순히 '최단 경로' 만 구하라고 한 것이 아니라 '최단 경로의 개수'를 구하라고 했다. 즉 특정 노드를 기준으로 그곳에 도착한 경로들의 개수들을 세어야 하고 이것은 동적 프로그래밍을 이용해서 메모이제이션해야한다.

 즉 BFS + DP 문제이다. (추후에 알게된 사실인데 BFS도 쓸 필요가 없이 2중 반복문을 돌려서도 해결이 가능하다.)

 

 

Solution

1. 메모이제이션을 위한 3차원 배열 dp를 둔다.
   1. dp[x][y][0] : (1, 1) ~ (x, y) 까지의 최단 거리
   2. dp[x][y][1] : (1, 1) ~ (x, y) 까지의 최단 경로 개수
2. BFS 반복문을 돌린다.
   1. 갈 수 있는 노드 중 아직 방문하지 않은 노드의 경우 (최초 방문)
      1. dp[next_x][next_y][0] = dp[now.x][now.y][0] + 1
      2. dp[next_x][next_y][1] = dp[now.x][now.y][1]
   2. 이미 방문한 노드의 경우
      1. 만약 next 노드의 최단거리보다 현재 노드 최단거리 + 1이 더 짧다면 dp[next_x][next_y][0] = dp[now.x][now.y][0] + 1
      2. next 노드의 최단거리와 현재 노드 최단거리 + 1이 같다면 next 노드의 최단 경로 개수 증가
   3. (m, n) 을 방문하면 종료
3. dp[m][n][1] 을 반환

 주의할 점은 %1,000,000,007을 까먹지 말아야한다. 이거 안하면 효율성 테스트 때 틀렸다고 나온다.

import java.util.*;


class Solution {

	int map[][];
	boolean visited[][] ;
	int dp[][][];

	public int solution(int m, int n, int[][] puddles) {

		map = new int[m+1][n+1];
		visited = new boolean[m+1][n+1];
		dp = new int[m+1][n+1][2]; //0 : 최단 거리, 1 : 최단 거리 개수

		//물에 잠긴 지역
		for(int i = 0;i < puddles.length;i++)
			map[puddles[i][0]][puddles[i][1]] = 1;

		bfs(m, n);

		return dp[m][n][1] % 1000000007;
	}

	public void bfs(int m, int n)
	{
		Queue<Position> queue = new LinkedList<>();
		queue.offer(new Position(1,1));
		visited[1][1] = true;
		dp[1][1][0] = 0;
		dp[1][1][1] = 1;

		while(!queue.isEmpty())
		{
			Position now = queue.poll();

			if(now.x == m && now.y == n)
				return;

			int x[] = {-1, 1, 0, 0};
			int y[] = {0, 0, -1, 1};

			for (int i = 0; i < 4; i++)
			{
				int next_x = now.x + x[i];
				int next_y = now.y + y[i];

				if (1 <= next_x && next_x <= m && 1 <= next_y && next_y <= n)
				{
					if (map[next_x][next_y] == 0)
					{
						//최초 방문
						if (!visited[next_x][next_y])
						{
							visited[next_x][next_y] = true;
							dp[next_x][next_y][0] = dp[now.x][now.y][0] % 1000000007 + 1;
							dp[next_x][next_y][1] = dp[now.x][now.y][1] % 1000000007;

							queue.offer(new Position(next_x,next_y));
						}
						//이미 방문한 노드
						else
						{
							//현재까지의 최단 거리보다 더 짧으면 새로운 최단 거리 부여
							if(dp[next_x][next_y][0] == 0 || dp[next_x][next_y][0] % 1000000007 > dp[now.x][now.y][0] % 1000000007 + 1)
							{
								dp[next_x][next_y][0] = dp[now.x][now.y][0] % 1000000007 + 1;
								dp[next_x][next_y][1] = dp[now.x][now.y][1] % 1000000007;
							}
							//현재까지의 최단 거리와 같으면 개수만 증가
							else if(dp[next_x][next_y][0] == dp[now.x][now.y][0] + 1)
							{
								dp[next_x][next_y][1] += dp[now.x][now.y][1] % 1000000007;
							}
						}
					}
				}
			}
		}
	}

	class Position
	{
		int x, y;

		public Position(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

}