[백준] G2 16137번 견우와 직녀 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

16137번: 견우와 직녀

[문제] 

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

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

예를 들어 오작교가 3분과 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. 먼저, 절벽이 교차하는 절벽인지, 아닌지를 찾아야 한다.

2. 교차하지 않는 절벽일 경우, 해당 절벽에 오작교(M)를 만들고 bfs탐색을 한다.

3. bfs탐색을 하면서 땅일 경우는 그냥 이동을 시키고 오작교일 경우 아래와 같은 조건을 만족해야 한다.

 다음 이동할 때의 시간(현재 이동한 시간 + 1) % 오작교의 생성 주기 == 0

4. 위 조건을 만족하는 경우는 해당 오작교를 건널 수 있으니 이동시켜준다.

5. 만족하지 않는다면 해당 오작교를 건널 수 없으니 현재 위치에서 시간만 증가시켜 준다.

6. bfs탐색을 종료하고 결괏값과 비교해 최솟값을 넣어준다.

7. 2번에서 만들어 둔 오작교(M)를 절벽(0)으로 다시 만들어주고 다음 절벽을 찾아 교차하는지 아닌지 찾는다.

8. 위 과정을 반복한다.

9. 모든 경우를 다 탐색 후, 최소 값을 출력한다.

[접근]

1. 이동을 하면서 최소 경로를 찾는 것이기 때문에 bfs로 접근하였다.

2. 탐색을 하면서 필요에 따라서 오작교를 생성하려고 하였는데 이 경우의 조건이 더 복잡해지는 것 같아 위의 풀이 방법으로 해결하였다.

[코드]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int M;
	static int ans;
	static int[][] map;
	static boolean[][] visited;
	
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	
	// 견우
	static class Altair {
		int x; // 현재 좌표
		int y; // 현재 y좌표
		int t; // 현재까지 걸린 시간
		
		Altair(int x, int y, int t){
			this.x = x;
			this.y = y;
			this.t = t;
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		ans = Integer.MAX_VALUE;
		
		map = new int[N][N];

		for(int r = 0; r < N; r++) {
			st = new StringTokenizer(br.readLine());
			
			for(int c = 0; c < N; c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 전체 배열을 탐색하면서 절벽인 곳을 찾아
		// 해당 절벽이 교차하는 곳인지를 확인한다.
		// 교차하는 곳이 아니라면 해당 위치에 오작교를 건설하고 탐색
		// 이후 돌아와서 해당 오작교를 다시 절벽으로 만들고 다음에 오는 교차하지 않는 절벽에 오작교 건설 후 탐색
		// 이를 반복하고 최종적으로 가장 적게 걸리는 것이 결과
		for(int r = 0; r < N; r++) {
			for(int c = 0; c < N; c++) {
				
				// 절별이라면
				if(map[r][c] == 0) {
					boolean[] check = new boolean[4];
					
					// 사방탐색
					for(int i = 0 ; i < 4 ; i++) {
						int nr = r + dr[i];
						int nc = c + dc[i];
						
						// 범위를 벗어나면
						if(nr >= N || nr < 0 || nc >= N || nc < 0)
							continue;

						// 탐색하는 곳이 절벽이라면
						if(map[nr][nc] == 0) {
							check[i] = true; // 해당 위치를 절벽으로 체크
						}
					}
					
					// 현재 절벽을 기준으로 위쪽과 왼쪽이 절벽이면 교차하는 절벽이다.
					if((check[0] && check[2]))
						continue;
					// 현재 절벽을 기준으로 위쪽과 오른쪽이 절벽이면 교차하는 절벽이다.
					else if (check[0] && check[3])
						continue;
					// 현재 절벽을 기준으로 아래쪽과 왼쪽이 절벽이면 교차하는 절벽이다.
					else if (check[1] && check[2])
						continue;
					// 현재 절벽을 기준으로 아래쪽과 오른쪽이 절벽이면 교차하는 절벽이다.
					else if (check[1] && check[3])
						continue;
					
					map[r][c] = M;
					visited = new boolean[N][N];
					
					bfs();
					
					map[r][c] = 0;
				}
			}
		}
		
		System.out.println(ans);
	}
	
	private static void bfs() {
		Queue<Altair> q = new LinkedList<>();
		visited[0][0] = true; // 0, 0에서 시작
		q.offer(new Altair(0, 0, 0));
		
		while(!q.isEmpty()) {
			Altair cur = q.poll();
			
			if(cur.x == N - 1 && cur.y == N - 1) {
				ans = Math.min(ans, cur.t);
				return;
			}
			
			for(int i = 0; i < 4; i++) {
				int nr = cur.x + dr[i];
				int nc = cur.y + dc[i];
				
				// 범위를 벗어나는 경우
				if(nr >= N || nr < 0 || nc >= N || nc < 0)
					continue;
				
				// 갈 수 없는 경우
				if(map[nr][nc] == 0 || visited[nr][nc])
					continue;
				
				// 땅인 경우 이동
				if(map[nr][nc] == 1) {
					visited[nr][nc] = true;
					
					q.offer(new Altair(nr, nc, cur.t + 1));
				}
				
				// 오작교가 생성된 절벽인 경우
				if(map[nr][nc] >= 2 && map[cur.x][cur.y] == 1) {
					// 만약 다음으로 이동을 할 때 시간을 오작교 주기로 나눠서 0이라면 이동 가능 
					if((cur.t + 1) % map[nr][nc] == 0) {
						visited[nr][nc] = true;
						
						q.offer(new Altair(nr, nc, cur.t + 1));
					} else {
						q.offer(new Altair(cur.x, cur.y, cur.t + 1));
					}
				}
			}
		}
	}
}