[백준 / BOJ] 21922번 : 학부 연구생 민상 - JAVA

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

21922번: 학부 연구생 민상

방향 바꾸는 조건

에어컨 바람이 사방으로 퍼져나가는 것이 아니라, 직선으로 움직이는 것을 먼저 알아야 한다. 가장 처음, 에어컨 위치에서만 사방으로 퍼지고 그 이후에는 (물건을 만나지 않는 이상) 한 방향으로 움직인다.

 

게다가 에어컨이 1개라는 보장은 없다. 예제 2처럼 에어컨이 2개 이상 나올 수 있기 때문에, 방 구조를 받다가 9 (에어컨) 가 나오면 거기에서 사방으로 퍼진 상태를 Queue에 담도록 했다.

 

Queue에 들어간 배열의 구성은 {행, 열, 이전에 움직인 방향} 이다. 이전 방향과 다음에 만날 물건으로 방향을 구해준다.

1. 빈 칸이면 이전 방향 그대로 움직인다.
2. 물건 1이 있으면 위/아래 방향일 때만 이전 그대로 움직인다.
3. 물건 2가 있으면 왼쪽/오른쪽 방향일 때만 이전 그대로 움직인다.
4. 물건 3이 있으면 위 - 오른쪽 / 아래 - 왼쪽 을 서로 바꿔 움직인다.
5. 물건 4가 있으면 위 - 왼쪽 / 아래 - 오른쪽 을 서로 바꿔 움직인다.

if문으로 하면 다음과 같다.

if(map[r][c] == 0) {
    d = dd; // 빈 칸이면 이전 방향 그대로 간다
} else if(map[r][c] == 1) {
    if(dd % 2 == 0) {
        d = dd; // 물건 1이 있으면 위/아래 방향일 때만 이전 그대로 간다
    }
} else if(map[r][c] == 2) {
    if(dd % 2 == 1) {
        d = dd; // 물건 2가 있으면 왼/오른쪽 방향일 때만 이전 그대로 간다
    }
} else if(map[r][c] == 3) {
	// 물건 3이 있으면 위 - 오른쪽 / 아래 - 왼쪽 이 서로 바뀐다.
    if(dd == 0) d = 3;
    else if(dd == 3) d = 0;
    else if(dd == 1) d = 2;
    else d = 1;

} else if(map[r][c] == 4){
	// 물건 4가 있으면 위 - 왼쪽 / 아래 - 오른쪽 이 서로 바뀐다.
    if(dd == 0) d = 1;
    else if(dd == 1) d = 0;
    else if(dd == 2) d = 3;
    else d = 2;

}

 

방문 체크

방문 체크는 3차원으로 진행했다. 같은 칸을 다른 방향에서 들어온다면 진행 방향이 당연히 달라지기 때문이다. 아래와 같은 상황에서 방향에 관계 없이 칸에 접근한 적이 있느냐만 판단한다면 오답이 나올 것이다.

방문 체크를 3차원 배열로 했기 때문에, 한 칸에 여러 번 방문할 우려가 있어 "방문한 칸"만 표시하는 배열 v2를 또 만들었다. 방문한 칸을 1로 초기화하기 때문에 나중에 다 끝나고 전부 더해주면 된다.

 

전체 코드

// 시간 : 1964ms
// 메모리 : 470408KB
public class Main {

	static int N;
	static int M;
	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());
		
		int[][] map = new int[N][M];
		
		int[] dr = {-1,0,1,0};
		int[] dc = {0,-1,0,1};
		
		int cnt = 0;
		Queue<int[]> que = new LinkedList<>();
		boolean[][][] v = new boolean[N][M][4];
		int[][] v2 = new int[N][M];
		
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j * 2) - '0';
				if(map[i][j] == 9) {
					for (int d = 0; d < 4; d++) {
						int nr = i + dr[d];
						int nc = j + dc[d];
						
						if(check(nr, nc)) continue;
						if(v[nr][nc][d]) continue;
						v[nr][nc][d] = true;
						que.offer(new int[] {nr, nc, d});
						v2[nr][nc] = 1;
					}
					v2[i][j] = 1;
				}
			}
		}
		
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			int r = cur[0];
			int c = cur[1];
			int dd = cur[2];
			
			int d = -1;
			if(map[r][c] == 0) {
				d = dd;
			} else if(map[r][c] == 1) {
				if(dd % 2 == 0) {
					d = dd;
				}
			} else if(map[r][c] == 2) {
				if(dd % 2 == 1) {
					d = dd;
				}
			} else if(map[r][c] == 3) {

				if(dd == 0) d = 3;
				else if(dd == 3) d = 0;
				else if(dd == 1) d = 2;
				else d = 1;
				
			} else if(map[r][c] == 4){

				if(dd == 0) d = 1;
				else if(dd == 1) d = 0;
				else if(dd == 2) d = 3;
				else d = 2;
				
			}
			
			if(d == -1) continue;
			int nr = r + dr[d];
			int nc = c + dc[d];
			
			if(check(nr, nc)) continue;
			if(v[nr][nc][d]) continue;
			v[nr][nc][d] = true;
			que.offer(new int[] {nr, nc, d});
			v2[nr][nc] = 1;
		}
		
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(v2[i][j] == 1) cnt++;
			}
		}
		
		System.out.println(cnt);
			
	}
	private static boolean check(int nr, int nc) {
		return nr >= N || nc >= M || nr < 0 || nc < 0;
	}

}