[Java] Progrmmers 코딩테스트 연습 : 등굣길 (동적 계획법 Dynamic Programming, BFS,Stack)

--- 문제 ---

 

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

 

--- 코드 ---

 

import java.util.*;

public class SchoolWay {

	public static void main(String[] args) {
		int m =4;
		int n=3; 
		int[][] puddles = {{2,2}};
		
		int[][] map = new int[n][m];
		long[][] count = new long[n][m];
		
		// 0. 환경 세팅 ( BFS 를 위한 Stack 설정 등 )
		for(int i=0; i<puddles.length; ++i) {
			map[puddles[i][1]-1][puddles[i][0]-1] = -1;
		}
		int[][] direction = {{1,0},{0,1}}; // 아래방향,오른쪽방향
		Queue<LinkedList<Integer>> check = new LinkedList<LinkedList<Integer>>();
		LinkedList<Integer> tmp = new LinkedList<Integer>();
		tmp.add(0);
		tmp.add(0);
		check.add(tmp);
		count[0][0]=1;
		
		// 1. BFS 시작
		while(!check.isEmpty()) {
			LinkedList<Integer> current = check.poll();
			int startx = current.get(0); // 세로 (x축) 의 현재 탐색 지점
			int starty = current.get(1); // 가로 (y축) 의 현재 탐색 지점
			
			if(startx == n-1 && starty ==m-1) {
				// 1-1. 마지막 도착지점인 경우 끝내기
				break;
			}
			
			for(int[] dir : direction) {
				int nextx = startx + dir[0];
				int nexty = starty + dir[1];
			
				if(nextx <n && nexty<m && map[nextx][nexty]!=-1) {
					// 1-2. 이동한 좌표가 지도 범위에 들어가는 경우
					
					int cost = map[startx][starty] +1 ;
					if( map[nextx][nexty]==0  ) {
						// 1-2-1. 지금껏 이 좌표에 도달한 경우가 없는 경우
						map[nextx][nexty] = cost;
						count[nextx][nexty] = count[startx][starty];
						tmp = new LinkedList<Integer>();
						tmp.add(nextx);
						tmp.add(nexty);
						check.add(tmp);
					}
					else if( cost == map[nextx][nexty]  ) {
						// 1-2-2. 현재 저장되어 있는 최소 경로가 지금 경로의 비용과 같은 경우
					   count[nextx][nexty] = ( count[nextx][nexty] + count[startx][starty] ) % 1000000007;
					   
					   
					}
					else if(cost < map[nextx][nexty]) {
						// 1-2-3. 현재 저장되어 있는 최소 경로가 더 큰 경우
						map[nextx][nexty] = cost;
						count[nextx][nexty] = count[startx][starty];
						continue;
					}
				}
			
			}
		}
		
		System.out.println((int)(count[n-1][m-1]% 1000000007));
 		
	}

}

 

--- 출처 ---

 

programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길