SWEA 1953 탈주범 검거(BFS, 구현)

SW Expert Academy

구현단계에서 생각보다 애를 먹었던 문제다.

문제접근은 시작점에서 bfs를 돌리면서 인접한 노드의 파이프모양에 따라 나아갈 수 있는 방향이 정해지고 그것을 카운트하는 방식인데 어떤 모양인지 체크하고 어떤 방향으로 갈지 체크하는 로직을 짜는데 시간이 많이 걸렸다.

 

먼저 상하좌우에 따라 각각 갈 수 있는 파이프의 번호를 저장해둔다(dir 배열)

dx, dy 방향벡터는 상하좌우로 이동할 수 있지만 지금 내가 위치한 파이프의 모양에 따라 상하좌우 중 특정 방향으로만 갈 수 있기 때문에 상하좌우의 벡터를 파이프의 개수 7개 만큼 dx[7][4], dy[7][4]로 만들어 이용한다

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

public class Solution {
	static int N,M,R,C,L,res;
	static int[][] board;
	static boolean[][] visited;
	static int[][] dx = {{0,0,0,0},{-1,1,0,0},{-1,1,0,0},{0,0,0,0},{-1,0,0,0},{0,1,0,0},{0,1,0,0},{-1,0,0,0}}; //1번 - 7번
	static int[][] dy = {{0,0,0,0},{0,0,-1,1},{0,0,0,0},{0,0,-1,1},{0,0,0,1},{0,0,0,1},{0,0,-1,0},{0,0,-1,0}};
	static int[][] dir = {{1,2,5,6}, {1,2,4,7}, {1,3,4,5}, {1,3,6,7}}; //상하좌우
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		
		for (int tc = 1; tc < T+1; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());
			
			
			board = new int[N][M];
			visited = new boolean[N][M];
			
			
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < M; j++) {
					board[i][j] = Integer.parseInt(st.nextToken());
 				}
			}
			res = 1;
			bfs();
			
			
			System.out.println("#"+tc+" "+res);

		}

	}
	
	
	public static void bfs() {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] {R,C,1});
		visited[R][C] = true;
				
		while(!queue.isEmpty()) {
			int[] temp = queue.poll();
			
			if (temp[2] == L)
				return;
			
			for (int j = 1; j < 8; j++) {
				if (board[temp[0]][temp[1]] == j) {
					for (int z = 0; z < 4; z++) {
						int nx = temp[0] + dx[j][z];
						int ny = temp[1] + dy[j][z];
						
						if(temp[0] == nx && temp[1] == ny) 
							continue;
						if (nx < 0 || ny < 0 || nx >= N || ny >= M)
							continue;
						if (board[nx][ny] == 0)
							continue;
						
						for(int k=0; k<4; k++) { 
							if(dir[z][k] == board[nx][ny]){ 
								if(!visited[nx][ny]){ 
									visited[nx][ny] = true;
									res++;
									queue.add(new int[] {nx,ny,temp[2]+1});
								}
							}
						}
						
						
					}
					
				}
			}
			
		}
		
		
		
	}
	

}