[백준] 16137번 견우와 직녀 골드2 - 자바(JAVA) / 시뮬레이션/ BFS

📑 문제

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

16137번: 견우와 직녀

문제

견우와 직녀는 여러 섬과 절벽으로 이루어진 지역에서 살고 있다. 이 지역은 격자로 나타낼 수 있으며, 상하좌우로 인접한 칸으로 가는 데 1분이 걸린다.

7월 7일은 견우와 직녀가 오작교를 건너 만날 수 있는 날이다. 그런데 고령화로 인해서 까마귀와 까치가 예전처럼 커다란 오작교를 만들 수 없다. 그래서 요즘은 일부 절벽에만 다리를 만들어 주고 있고, 그마저도 힘들어서 몇 분 주기로 오작교를 짓고 해체하는 작업을 반복해야 한다. 한 번 지은 오작교는 1분 동안 유지할 수 있다.

예를 들어 오작교가 3분과 4분 주기라면, 건널 수 있는 시간은 아래 그림에서 초록색으로 표시한 부분과 같다.

T = 3	T = 4

오작교는 이처럼 매우 불안정하므로, 견우는 안전을 위해 두 번 연속으로 오작교를 건너지는 않기로 했다.

까마귀와 까치는 조금이라도 견우를 더 도와주기 위해, 절벽을 정확히 하나 골라 주기가 M분인 오작교를 하나 더 놓아 주기로 했다. 단, 이미 오작교를 짓기로 예정한 절벽에는 오작교를 하나 더 놓을 수 없고, 아래와 같이 절벽이 가로와 세로로 교차하는 곳에도 오작교를 놓을 수 없다.

견우가 직녀에게 도착할 수 있는 최소의 시간을 찾아 보자.

 

입력

첫째 줄에 지형의 행과 열의 크기를 나타내는 정수 N (2 ≤ N ≤ 10)과 새로 만들어지는 오작교의 주기를 의미하는 정수 M(2 ≤ M ≤ 20)이 주어진다.

다음 N개의 줄에는 줄마다 배열의 각 행을 나타내는 N개의 정수가 한 개의 빈칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 20 이하이다.

또한, 각 칸에 들어가는 정수의 의미는 다음과 같다.

• 1: 이동할 수 있는 일반적인 땅
• 0: 건널 수 없는 절벽
• 2 이상의 수: 적혀있는 수 만큼의 주기를 가지는 오작교

견우의 시작점은 지형의 맨 왼쪽 위 (0, 0) 이고, 직녀가 사는 곳은 지형의 맨 오른쪽 아래인 (N-1, N-1)이다. 견우가 시작점에서 출발하는 시간은 0분이다. 견우와 직녀가 사는 곳은 일반적인 땅이다.

견우와 직녀가 무조건 만날 수 있는 경우만 주어진다. 또한, 주어지는 지형 정보에서 오작교를 반드시 하나 이상 놓을 수 있다. 절벽이 가로와 세로로 교차하는 지점에는 오작교가 설치되어 있지 않다.

출력

견우가 직녀에게 갈 수 있는 최소의 시간을 출력한다.

 

 

 

 

 

 

 

 

 

✒️ 풀이

 

💡 문제를 이해하기 위해서는 꼭 짚고 넘어가야 하는 포인트가 있다.

 

 1. 오작교는 주기에 맞춰서만 건널 수 있다. 현재 시간이 T초라면, 다음 위치가 오작교일 때 T+1초가 오작교의 주기와 맞아야 건널 수 있는 것이다. 따라서 현재 위치에서 오작교로 건너가려 할 때, (T+1)%(오작교 주기)가 0이 되어야 건널 수 있다.

 

 2. 주기가 맞지 않더라도, 기다렸다가 건너는 방법도 고려해야 한다.

 

 3. 두 번 연속 오작교를 건너지는 않는다. 현재 서있는 위치가 오작교 위라면, 다음 위치로 오작교를 고를 수 없다.

 

 4 절벽이 교차하는 케이스는 미리 체크하여 아예 이동시 고려하지 않도록 처리한다. 코드에서는 값을 -1로 넣어주었다. 일반 땅(1), 절벽(0), 오작교(2 이상의 값)으로 표현되므로 -1로 처리한 교차지역은 코드 진행시 고려되지 않는다.

 

 5. 다음 위치가 절벽이라도, 새 오작교를 아직 놓지 않은 경우에 한해 그 절벽에 오작교를 새로 설치하고 넘어갈 수 있다. 맥락 상으로는 시작 시에 절벽 중 한 곳을 골라 새 오작교를 먼저 설치해두고 출발하지만, 어느 곳에 놓는 것이 최적인지 바로 고려할 수 없다. 따라서 일단 출발을 하고, 오작교를 설치한 경우/ 설치하지 않은 경우의 케이스를 모두 들고 다니며, 오작교를 아직 설치하지 않은 경우에 절벽을 만나면 그때 그 곳에 오작교가 설치되어 있고 그 위를 건넌다고 생각하고 넘어가는 것이다. 이 때 주기를 계산하는 방법은 1번을 따른다.

 

 6. 직녀의 위치에 도착하면 바로 리턴한다.

 

 

 

 

📑 정리

 ✔️ 지도를 입력받은 후, 교차지역을 체크 및 처리(-1을 저장)해놓는다.

 ✔️ BFS 탐색을 시작한다.

 ✔️ 사방탐색 시 아래 순서대로 고려한다.

    (1) 다음 위치가 땅일 때: 넘어간다.

    (2) 다음 위치가 오작교 위일 때:

         -1) 현재 위치가 땅일 경우: 주기에 맞으면 다음 위치로, 맞지 않으면 대기를 위해 현재 위치를 큐에 넣는다.

         -2) 현재 위치가 오작교 위일 경우: 넘어가지 않는다.

    (3) 다음 위치가 절벽일 때:

         -1) 이미 새 오작교를 설치해서 넘어온 적이 있는 경우: 넘어가지 않는다.

         -2) 새 오작교를 설치한 적이 없는 경우: 오작교를 설치했다고 고려하고 (2)번으로 간다.

 

 

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

public class Main_백준_16137_견우와직녀_골드2 {

	/**
	 * 오작교 주기 있음 = T%주기==0이어야 건널 수 있다. 건너는데 1초
	 * 두 번 연속으로 오작교를 건너지는 않는다 = 이미 오작교 위면 또 오작교 위로 가지 않는다.
	 * 
	 * visited[r][c][k]: k=0(새로 놓은 오작교가 없음) or 1(새로 오작교 놓고 건넘)
	 * 1. BFS
	 * 2. 현재 위치가 오작교 위가 아니고(1) 건널 수 있는 오작교가 있으면 건넌다.
	 * 3. 새로 오작교를 놓을 수 있는 경우 놓고 건넌다.
	 * 4. 직녀에게 도착하면 최소시간을 리턴한다.
	 * */
	
	static int N, M, result = Integer.MAX_VALUE;
	static int[][] map;
	static boolean[][][] visited;
	static int[] dr = {1, -1, 0, 0};
	static int[] dc = {0, 0, 1, -1};
	
	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][N];
		visited = new boolean[N][N][2];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}//input
		
		findCross();
		bfs();
		System.out.println(result);
	}//end of main
	
	private static void findCross() {
		
		int cnt = 0;
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				if(map[r][c]==0) {	// 절벽일 때
					cnt=0;
					// 좌상/ 좌하/ 우상/ 우하
					if((r-1>=0 && map[r-1][c]==0) || (r+1<N && map[r+1][c]==0)) cnt++;
					if((c-1>=0 && map[r][c-1]==0) || (c+1<N && map[r][c+1]==0)) cnt++;
					if(cnt==2) map[r][c]=-1;
				}
			}
		}
	}
	
	private static void bfs() {
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.offer(new int[] {0,0,0,0});//r,c,k,t
		visited[0][0][0] = true;
		
		while(true) {
			int[] cur = queue.poll();
			int r = cur[0];
			int c = cur[1];
			int k = cur[2];
			int t = cur[3];
			int nr, nc, nt=t+1;
			
			if(r==N-1 && c==N-1) {
				result = t;
				break;
			}
			
			for (int i = 0; i < 4; i++) {
				nr = r + dr[i];
				nc = c + dc[i];
				
				if(nr<0||nc<0||nr>=N||nc>=N||visited[nr][nc][k]) continue;
				
				if(map[nr][nc]==1) { // 다음 위치가 땅일 때
					visited[nr][nc][k] = true;
					queue.offer(new int[] {nr, nc, k, nt});
				}
				if(map[nr][nc]>1) { // 다음 위치가 오작교 위일 때
					if(map[r][c]==1) {// 현재 위치가 땅이어야만 이동가능
						if(nt%map[nr][nc]==0) {// 이동가능하면
							queue.offer(new int[] {nr, nc, k, nt});
						}else {
							queue.offer(new int[] {r, c, k, nt});
						}
					}
				}
				if(map[nr][nc]==0 && k==0) { // 다음 위치가 땅일 때
					if(nt%M==0) queue.offer(new int[] {nr,nc,k+1,nt});
					else queue.offer(new int[] {r,c,k,nt});
				}
			}
		}
	}
}//end of class

 

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨