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

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

21922번: 학부 연구생 민상

 

21922번: 학부 연구생 민상

 

※ 문제 풀 때 주의 사항

(1) boolean 타입 3차원 배열(boolean[][][] visit)을 이용해서 풀어야 한다. 

   -> boolean 3차원 배열로 풀지 않고 int 타입 2차원 배열을 새로 만들어서 지나가는 곳마다 값을 누적해서 0이 아닌 곳을 카운트 했더니 시간초과가 발생했다.

(2) 방문했던 위치는 또 다시 방문하지 않도록 해야한다.

   -> if(visit[ny][nx][cur.dir]) continue; // 필수로 넣어야 시간초과가 발생하지 않는다.

(3) switch문에서 1,2번 물건에서 제한되는 방향일 때 continue를 하더라도 break;를 빼먹지 말아야 한다.

   -> 제한되지 않는 케이스는 이어지는 케이스에 걸려서 이상한 결과가 나온다.

 

package simulation;

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 Minsang {
	static int[][] map = new int[2001][2001];
	static int N, M, cnt;
	static boolean[][][] visit;
    // 인덱스에 따른 방향 : 0 : ↑, 1 : →, 2 : ↓, 3 : ←
	static int[] dx = {0, 1, 0, -1};	
	static int[] dy = {-1, 0, 1, 0};
	static class Node {
		int y, x, dir;
		public Node(int y, int x, int dir) {
			this.y = y;
			this.x = x;
			this.dir = dir;
		}
	}
	
	static Queue<Node> q = new LinkedList<Node>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		visit = new boolean[N][M][4];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				int temp = stoi(st.nextToken());
				if(temp == 9) {
					for (int dir = 0; dir < 4; dir++) {
						visit[i][j][dir] = true;
						q.add(new Node(i, j, dir));
					}
				}
				map[i][j] = temp;
			}
		}
		
		bfs();
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				for (int dir = 0; dir < 4; dir++) {
					if(visit[i][j][dir]) {
						cnt++;
						break;
					}
				}
			}
		}
		
		System.out.println(cnt);
	}
	
	public static void bfs() {
		while(!q.isEmpty()) {
			Node cur = q.poll();
			
			int nx = cur.x + dx[cur.dir];
			int ny = cur.y + dy[cur.dir];
			
			if(nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
			if(visit[ny][nx][cur.dir]) continue;
			
			visit[ny][nx][cur.dir] = true;
			
			switch(map[ny][nx]) {
			case 1 :
				if(cur.dir == 1 || cur.dir == 3) continue;
				break;
			case 2 :
				if(cur.dir == 0 || cur.dir == 2) continue;
				break;
			case 3 :
				if(cur.dir == 0) cur.dir = 1;
				else if(cur.dir == 1) cur.dir = 0;
				else if(cur.dir == 2) cur.dir = 3;
				else if(cur.dir == 3) cur.dir = 2;
				break;
			case 4 :
				if(cur.dir == 0) cur.dir = 3;
				else if(cur.dir == 1) cur.dir = 2;
				else if(cur.dir == 2) cur.dir = 1;
				else if(cur.dir == 3) cur.dir = 0;
				break;
			}
			
			q.add(new Node(ny, nx, cur.dir));
		}
	}
	
	public static int stoi(String str) {
		return Integer.parseInt(str);
	}
}