1953 탈주범 검거

 

DFS로 시도했으나 오답이다 이유를 생각해보면, DFS는 한붓그리기 라고 생각하면 된다.

파이프를 최단거리로 지나가는 경우도 생각할 수 있지만, 빙 돌아가는 경우에는 Level에 대한 부분이 애매해져버린다.

다른 풀이를 보니 visited 배열을 잘 사용해서 풀이 하는 경우가 있는것 같으나  visited를 구성하는 것이 번거로워 bfs로 변경함 ( 문제를 많이 풀다 보면, 둘을 번갈아가며 구현하는데 큰 어렴은 없다.)

 

단순하게 풀이하려 노력했다.

각 파이프 모양에서 나올 수 있는 움직임을 2차원 배열인 dx,dy로 저장.

 

보통의 bfs에서는 다음 단계(nr,nc)로 이동하고 보통 끝나지만 파이프가 연결됐는지 확인하기 위해

이동한 좌표(nrnr,ncnc) 에서 원래의 파이프(nr,nc)로 돌아올 수 있는지 확인을 하고 Q에 넣어주면 된다.

 

다른 사람들은 타입별로 파이프를 매핑해서 풀었는데, 이 방법이 더 직관적이지 않나 하는 생각이 든다.

 

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


class Solution {

	static int N, M, R, C, L;
	static int[][] dx = { {}, { 1, -1, 0, 0 }, { 1, -1 }, { 0, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 }, { -1, 0 } };
	static int[][] dy = { {}, { 0, 0, -1, 1 }, { 0, 0 }, { 1, -1 }, { 1, 0 }, { 1, 0 }, { 0, -1 }, { 0, -1 } };
	static int[][] map;
	static boolean[][] visited;
	static int answer;
	private static boolean DBG = false;

	public static void main(String args[]) throws Exception {


		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T;
		T = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		for (int test_case = 1; test_case <= T; test_case++) {

			StringTokenizer st = new StringTokenizer(br.readLine());
			answer = 0;
			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());
			map = 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++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			//dfs(0, R, C);
			bfs();
			
			sb.append(String.format("#%d %d\n",test_case, answer));
			//System.out.println(answer);
		}
		
		System.out.println(sb);
	}

	private static void bfs() {
		Queue<int []> Q = new LinkedList<>();
		
		Q.offer(new int[]{R,C});
		
		int level = 0 ; 
		while(!Q.isEmpty()) {
			
			if( level ==L) {
				return;
			}
			
			
			int size = Q.size();
			for ( int t = 0 ; t < size ; t++) {
				int[] pos =Q.poll();
				int r= pos[0], c=pos[1];
				if (visited[r][c])
					continue;
				
				visited[r][c] = true;
				answer++;
				
				int now = map[r][c];
				for (int i = 0; i < dx[now].length; i++) {
					
					int nr = r + dx[now][i];
					int nc = c + dy[now][i];
										
					if (nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc]!=0&& !visited[nr][nc]) {
						int next = map[nr][nc];
						if(DBG)
						System.out.printf("from[%d %d]to[%d %d]next map : %d visited : %b\n",r,c, nr,nc,next,visited[nr][nc] );
						for (int j = 0; j < dx[next].length; j++) {						
							int nrnr = nr + dx[next][j];
							int ncnc = nc + dy[next][j];						
							if (nrnr >= 0 && nrnr < N && ncnc >= 0 && ncnc < M && 
									nrnr == r && ncnc == c) {
								if(DBG)
								System.out.printf("offer[%d %d]next : %d\n", nr,nc,next);
								Q.offer(new int[] {nr,nc});
							}

						}

					}
				}
				
				
			}
			
			level ++;
			if(DBG)
			System.out.println("level : "+level);
			
		}
		
		
	}

	private static void dfs(int level, int r, int c) {

		if (visited[r][c])
			return;
		
		visited[r][c] = true;
		if(DBG)
		System.out.printf("visited [%d %d] set true\n", r,c, visited[r][c]);
		answer++;
		if(DBG)
		System.out.printf("enter & count [%d %d] %d\n", r,c ,answer);

		if (level == L+1) {
			return;
		} else {
			int now = map[r][c];
			for (int i = 0; i < dx[now].length; i++) {
				
				int nr = r + dx[now][i];
				int nc = c + dy[now][i];
				
				
				if (nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc]!=0&& !visited[nr][nc]) {
					int next = map[nr][nc];
					if(DBG)
					System.out.printf("from[%d %d]to[%d %d]next map : %d visited : %b\n",r,c, nr,nc,next,visited[nr][nc] );
					for (int j = 0; j < dx[next].length; j++) {						
						int nrnr = nr + dx[next][j];
						int ncnc = nc + dy[next][j];						
						if (nrnr >= 0 && nrnr < N && ncnc >= 0 && ncnc < M && 
								nrnr == r && ncnc == c) {
							if(DBG)
							System.out.printf("dfs[%d %d]next : %d\n", nr,nc,next);
							dfs(level + 1, nr, nc);
						}

					}

				}
			}

		}

	}
}