[Java] swea 1953 탈주범검거

[Java] swea 2382  미생물격리[Java] swea 1953 탈주범검거

 

 

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq&categoryId=AV5PpLlKAQ4DFAUq&categoryType=CODE&problemTitle=sw&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2

SW Expert Academy

 

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

public class 모의SW_1953_탈주범검거 {
	static int N, M, R, C, L;
	static int[][] map;

	static class Pos {
		int x, y, cnt;

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

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		for (int testcase = 1; testcase <= T; testcase++) {
			StringTokenizer 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());

			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());
				}
			}

			CNT = 0;
			solve();

			System.out.println("#" + testcase + " " + CNT);
		} // tc

	} // main

	static int CNT;
	static boolean[][] visited;
	static int[][] dir = new int[][] { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };

	private static void solve() {
		Queue<Pos> q = new LinkedList<>();

		visited[R][C] = true;
		q.add(new Pos(R, C, 1));

		while (!q.isEmpty()) {
			Pos p = q.poll();
			CNT++;
			if (p.cnt == L) continue;

			int curPipe = map[p.x][p.y];
			for (int d = 0; d < 4; d++) {
				if(!canGo(curPipe, d)) continue;
				int nx = p.x + dir[d][0];
				int ny = p.y + dir[d][1];
				if (nx < 0 || nx >= N || ny < 0 || ny >= M || visited[nx][ny] || map[nx][ny] == 0
						|| !canGoNextPipe(map[nx][ny], d))
					continue;
				visited[nx][ny] = true;
				q.add(new Pos(nx, ny, p.cnt+1));
			}

		} // while

	} // solve

	static boolean canGo(int curPipe, int d) { // 현재 curPipe에서 d방향으로 갈 수 있는가?
		switch (curPipe) {
		case 1: return true;
		case 2:
			if(d == 0 || d == 2) return true;
			break;
		case 3:
			if(d == 1 || d == 3) return true;
			break;
		case 4:
			if(d == 0 || d == 1) return true;
			break;
		case 5:
			if(d == 1 || d == 2) return true;
			break;
		case 6:
			if(d == 2 || d == 3) return true;
			break;
		case 7:
			if(d == 0 || d == 3) return true;
			break;
		}
		
		return false;
	} // canGo
	
	static boolean canGoNextPipe(int pipeNum, int d) {
		switch (d) {
		case 0:
			if(pipeNum == 1 || pipeNum == 2 || pipeNum == 5 || pipeNum == 6) {
				return true;
			}
			break;
		case 1:
			if(pipeNum == 1 || pipeNum == 3 || pipeNum == 6 || pipeNum == 7) {
				return true;
			}
			break;
		case 2:
			if(pipeNum == 1 || pipeNum == 2 || pipeNum == 4 || pipeNum == 7) {
				return true;
			}
			break;
		case 3:
			if(pipeNum == 1 || pipeNum == 3 || pipeNum == 4 || pipeNum == 5) {
				return true;
			}
			break;
		}

		return false;
	} // getDirs
	
}

 

참 하드코딩스러운..

 

bfs로 맨홀뚜껑부터 큐에 add하여 4방향으로 다 이동해보는데, 현재 파이프에서 그 방향으로 이동할 수 있는지 확인하는 canGo(예로 들어 내가 2번파이프에 있다면 ↑, ↓ 방향으로만 움직일 수 있다.) 를 통과하면

 

방문하지 않았고 파이프가 없는 땅도 아니고 canGoNextPipe(현재 방향으로 갔을 때 갈 수 있는 파이프인지. 예로 들어 내가 1방향으로 가는 것이라면 파이프 1, 3, 6, 7 으로만 갈 수 있을 것이다.) 를 통과했다면

 

큐에 넣는다.

 

이 때 count 변수를 둬서 L 이 되었다면 더이상 다시 큐에 넣지 않는다.

 

이 작업을 큐가 빌 때까지 계속 하면 총 갈 수 있는 땅 수가 나온다.