[SWEA] 1953. 탈주범 검거

BFS를 이용한 나의 풀이

• 메모리 : 26,332 KB
• 실행시간 : 126 ms
• 코드길이 : 3,594 B
• 소요시간 : 1H 10M

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 Solution_1953_탈주범검거 {

	static int N, M, R, C, L, ans;
	static Queue<Point> queue;
	static boolean[][] visited;
	static int[][] map;
	static int[][] delta = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder answer = new StringBuilder();
		StringTokenizer st = null;
		int T = Integer.parseInt(in.readLine());
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(in.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());
			map = new int[N][M];
			visited = new boolean[N][M];
			ans = 0;
			
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(in.readLine()," ");
				for (int j = 0; j < M; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			} // end input
			
			answer.append('#').append(tc).append(' ').append(bfs()).append('\n');
		} // end test-case
		
		System.out.print(answer);
		in.close();
	} // end main

	private static int bfs() {
		queue = new LinkedList<Point>();
		queue.add(new Point(R,C));
		visited[R][C] = true;
		
		int size, time = 0;
		while(!queue.isEmpty()) {
			size = queue.size();
			time++;
			while(--size >= 0) {
				connect(queue.poll());
				ans++;
			}
			
			if(time == L)
				break;
		}
		queue.clear();
		return ans;
	}

	private static void connect(Point cur) {
		switch (map[cur.x][cur.y]) {
		case 1: // 상하좌우 터널과 연결
			for (int d = 0; d < delta.length; d++) {
				find(cur,d);
			}
			break;
		case 2: // 상하 터널과 연결
			find(cur,0);
			find(cur,2);
			break;
		case 3: // 좌우 터널과 연결
			find(cur,1);
			find(cur,3);
			break;
		case 4: // 상우 터널과 연결
			find(cur,0);
			find(cur,1);
			break;
		case 5: // 하우 터널과 연결
			find(cur,2);
			find(cur,1);
			break;
		case 6: // 하좌 터널과 연결
			find(cur,2);
			find(cur,3);
			break;
		case 7: // 상좌 터널과 연결
			find(cur,0);
			find(cur,3);
			break;
		}
	}
	
	
	private static void find(Point cur, int d) {
		visited[cur.x][cur.y] = true;
		int curX, curY;
		curX = cur.x + delta[d][0];
		curY = cur.y + delta[d][1];
		if (curX >= 0 && curX < N && curY >= 0 && curY < M && !visited[curX][curY] && map[curX][curY] > 0) {
			switch (d) {
			case 0: // 상
				if(map[curX][curY] == 1 || map[curX][curY] == 2 || map[curX][curY] == 5 || map[curX][curY] == 6) {
					queue.add(new Point(curX, curY));
					visited[curX][curY] = true;
				}
				break;
			case 1: // 우
				if(map[curX][curY] == 1 || map[curX][curY] == 3 || map[curX][curY] == 6 || map[curX][curY] == 7) {
					queue.add(new Point(curX, curY));
					visited[curX][curY] = true;
				}
				break;
			case 2: // 하
				if(map[curX][curY] == 1 || map[curX][curY] == 2 || map[curX][curY] == 4 || map[curX][curY] == 7) {
					queue.add(new Point(curX, curY));
					visited[curX][curY] = true;
				}
				break;
			case 3: // 좌
				if(map[curX][curY] == 1 || map[curX][curY] == 3 || map[curX][curY] == 4 || map[curX][curY] == 5) {
					queue.add(new Point(curX, curY));
					visited[curX][curY] = true;
				}
				break;
			}
		}
	}

	static class Point {
		int x;
		int y;
		
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

BFS를 이용한 교수님 풀이

• 메모리 : 26,556 KB
• 실행시간 : 129 ms
• 코드길이 : 2,635 B

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 Solution_1953_탈주범검거_수업_BFS {

	static int N, M, R, C, L, ans;
	static Queue<Point> queue;
	static boolean[][] visited;
	static int[][] map;
	static int[][] delta = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
	static int[][] block_hole = { {}, // 0번 블럭 없음
			{ 1, 1, 1, 1 }, 
			{ 1, 0, 1, 0 }, 
			{ 0, 1, 0, 1 }, 
			{ 1, 1, 0, 0 }, 
			{ 0, 1, 1, 0 }, 
			{ 0, 0, 1, 1 },
			{ 1, 0, 0, 1 } };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder answer = new StringBuilder();
		StringTokenizer st = null;
		int T = Integer.parseInt(in.readLine());
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(in.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());
			map = new int[N][M];
			visited = new boolean[N][M];

			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(in.readLine(), " ");
				for (int j = 0; j < M; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			} // end input

			
			answer.append('#').append(tc).append(' ').append(bfs()).append('\n');
		} // end test-case

		System.out.print(answer);
		in.close();
	} // end main

	private static int bfs() {
		queue = new LinkedList<Point>();
		queue.add(new Point(R, C));
		visited[R][C] = true;

		int size, time = 1;
		while (!queue.isEmpty() && time < L) {
			size = queue.size();
			while (--size >= 0) {
				Point now = queue.poll();
				int block = map[now.x][now.y];

				for (int d = 0; d < 4; d++) {
					// 현재 서 있는 블럭에 방향 d가 뚫려있는지
					if (block_hole[block][d] == 1) {
						int ni = now.x + delta[d][0];
						int nj = now.y + delta[d][1];

						if (ni >= 0 && ni < N && nj >= 0 && nj < M && map[ni][nj] > 0 && !visited[ni][nj]
								&& block_hole[map[ni][nj]][(d + 2) % 4] == 1) {
							visited[ni][nj] = true;
							queue.add(new Point(ni, nj));
						}
					}
				}
			} // end sec while
			time++;
		} // end first while
		ans = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (visited[i][j])
					ans++;
			}
		}
		return ans;
	}

	static class Point {
		int x;
		int y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

DFS를 이용한 교수님 풀이

• 메모리 : 25,960 KB
• 실행시간 : 141 ms
• 코드길이 : 2,399 B

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution_1953_탈주범검거_수업_DFS {

	static int N, M, R, C, L, ans;
	static int[][] map;
	static int[][] delta = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
	static int[][] block_hole = { 
			{}, // 0번 블럭 없음
			{ 1, 1, 1, 1 }, 
			{ 1, 0, 1, 0 }, 
			{ 0, 1, 0, 1 }, 
			{ 1, 1, 0, 0 }, 
			{ 0, 1, 1, 0 }, 
			{ 0, 0, 1, 1 },
			{ 1, 0, 0, 1 } };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder answer = new StringBuilder();
		StringTokenizer st = null;
		int T = Integer.parseInt(in.readLine());
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(in.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());
			map = new int[N][M];

			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(in.readLine(), " ");
				for (int j = 0; j < M; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			} // end input

			// dfs 사용시
			visited2 = new int[N][M];
			for (int[] row : visited2) {
				Arrays.fill(row, Integer.MAX_VALUE);
			}

			dfs(R, C, 1);
			ans = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (visited2[i][j] != Integer.MAX_VALUE)
						ans++;
				}
			}
			answer.append('#').append(tc).append(' ').append(ans).append('\n');
		} // end test-case

		System.out.print(answer);
		in.close();
	} // end main

	static int[][] visited2;

	private static void dfs(int i, int j, int time) {
		if (time == L + 1)
			return;

		visited2[i][j] = time;
		int block = map[i][j];

		for (int d = 0; d < 4; d++) {
			// 현재 서 있는 블럭에 방향 d가 뚫려있는지
			if (block_hole[block][d] == 1) {
				int ni = i + delta[d][0];
				int nj = j + delta[d][1];

				if (ni >= 0 && ni < N && nj >= 0 && nj < M && map[ni][nj] > 0 && (time < visited2[ni][nj])
						&& block_hole[map[ni][nj]][(d + 2) % 4] == 1) {
					dfs(ni, nj, time + 1);
				}
			}
		}
	}

	static class Point {
		int x;
		int y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}