백준 - 16137 견우와 직녀

www.acmicpc.net/problem/16137

16137번: 견우와 직녀

 

1. 유형

구현, BFS

 

2. 풀이

문제의 설명을 완벽히 이해하는 것이 어려웠습니다.

 

고려할 사항이 몇가지 있습니다.

- 교차로에서는 오작교를 놓지 못한다

- 연속으로 오작교를 건너지 못한다

- 주기가 맞아야지 오작교를 건널 수 있다

위의 3가지 경우를 주의 해야 합니다.

 

모듈화

input() - 입력함수

bfs() - bfs돌리기

 

풀이방식은 bfs를 돌리면서 다음에 올 수 있는 값이 0일때, 1일때, 2이상일떄로 경우의 수를 나누어

판단합니다.

방문처리는 오작교를 한번 놓았는지 아닌지에 대해 다음 경우의 수가 달리짐으로, 3차원 배열을 처리해야 합니다.

 

교차로 처리

 

bfs를 돌리다가 다음값으로 0을 만난경우, 2가지 경우의수가 있습니다.

주기가 맞지 않아 대기하는 경우,

주기가 맞아 이동할수 있는 경우

1을 만난경우는 그냥 이동시켜주면 됩니다.

 

2이상(오작교)를 만난경우

3. 디버깅 실수

2를 만났을 경우 visited[0][nr][nc]로 처리해서 시간을 많이 잡아먹었다.

위에서도 설명한거 처럼, 이때는 내가 가지고 있는 오작교를 놓을 수 있는 기회를 사용하지 않은 상태이고,

처음 주어지는 오작교를 사용한 것이다. 따라서 cur.use를 그대로 넣어줘야한다.

 

0을 만났을 경우, 이때에도 대기를 해줘야하는 경우가 있었다.

4 10

1 1 0 1

0 0 0 0

1 1 0 1

1 1 13 1

이런 경우를 생각하지 못했다.

 

이처럼 반례가 많고 지문 자체를 이해하기도 힘든 문제였다.

 

4. 코드

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

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, M, map[][], ans;
	static boolean visited[][][];
	static int dr[] = { -1, 1, 0, 0 };
	static int dc[] = { 0, 0, -1, 1 };

	static class Node {
		int r, c, t, use;

		public Node(int r, int c, int t, int use) {
			this.r = r;
			this.c = c;
			this.t = t;
			this.use = use;
		}
	}

	static void input() throws IOException {
		st = new StringTokenizer(in.readLine());
		N = Integer.valueOf(st.nextToken());
		M = Integer.valueOf(st.nextToken());
		map = new int[N][N];
		visited = new boolean[2][N][N];
		ans = Integer.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.valueOf(st.nextToken());
			}
		}
		// 교차로 체크
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int cnt = 0;
				if (map[i][j] == 0) {
					if ((i - 1 >= 0 && map[i - 1][j] == 0) || (i + 1 < N && map[i + 1][j] == 0))
						cnt++;
					if ((j - 1 >= 0 && map[i][j - 1] == 0) || (j + 1 < N && map[i][j + 1] == 0))
						cnt++;
				}
				if (cnt == 2)
					map[i][j] = -1;
			}
		}
	}

	static void bfs() {
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(0, 0, 0, 1));
		visited[1][0][0] = true;
		while (!q.isEmpty()) {
			Node cur = q.poll();
			if(cur.r==N-1 && cur.c==N-1) {
				ans = Math.min(ans, cur.t);
				return;
			}
			for (int i = 0; i < 4; i++) {
				int nr = cur.r + dr[i];
				int nc = cur.c + dc[i];
				int nt = cur.t + 1;
				if (nr < 0 || nr >= N || nc < 0 || nc >= N || map[nr][nc] == -1)
					continue;
				if (map[nr][nc] == 0) {
					// 대기
					if (nt % M != 0) {
						q.add(new Node(cur.r, cur.c, cur.t + 1, cur.use));
					} else if (cur.use>0 && map[cur.r][cur.c] == 1 && !visited[0][nr][nc]) {// 연속이지 않고 방문하지 않은곳
						visited[0][nr][nc] = true;
						q.add(new Node(nr, nc, nt, 0));
					}
				} else if (map[nr][nc] == 1 && !visited[cur.use][nr][nc]) {
					visited[cur.use][nr][nc] = true;
					q.add(new Node(nr, nc, nt, cur.use));
				} else if (map[nr][nc] >= 2) {
					// 대기
					if (nt % map[nr][nc] != 0) {
						q.add(new Node(cur.r, cur.c, nt, cur.use));
					}
					// 이동
					else if (map[cur.r][cur.c] == 1 && !visited[cur.use][nr][nc]) {
						visited[cur.use][nr][nc] = true;
						q.add(new Node(nr, nc, nt, cur.use));
					}
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		input();
		bfs();
		System.out.println(ans);
	}
}