알고리즘/SWEA
SWEA 모의 1963 탈주범 검거
은서파
2020. 6. 8. 23:32
SWEA 모의 1963 탈주범 검거
문제링크
http://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.
핵심 컨셉
고려사항
* 파이프 정보
- 파이프는 1~7까지 고정된 형태로 주어지며 들어가는 구멍과 나가는 구멍이 중요
- boolean[][] 형태에 열린 공간은 true로 설정
- 이때 방향은 북쪽을 0으로 해서 시계방향으로 맞춰야 나중에 사방탐색 할 때나 파이프간의 연결을 확인할 때 수월하다.
* 탐색
- 가장 기본적으로는 맨홀의 위치에서 사방 탐색으로 주어진 시간 동안 방문할 수 있는 모든 지점들의 개수를 출력하는 문제
- 사방 탐색 과정에서 4 방향을 모두 갈 수 있는 것이 아니라 파이프의 타입에 따라서 갈수 있는 지점이 한정된다.
- 또한 이동할 수 있다고 하더라고 다음 지점에서 탈주범을 받아줄 수 있어야 한다.
- 다음 지점에 탈주범이 도달하려면 현재 파이프와 다음 파이프가 연결되어야 하는데
- 이를 쉽게 하기 위해 북쪽(0)번에서 시계방향으로 방향을 정해서
- 1, 3번과 0, 2번이 짝이 된다면 (내꺼+2)/4를 하면 상대편꺼가 나옴 1의 상대는 -> 3, 4의 상대는 2
- 또한 주어진 시간을 넘어가면 탐색을 종료해줘야 함
* 시간의 측정
- 한번의 BFS 탐색에 한 시간이 소요되며 최대 L 시간까지 도망갈 수 있음
- 최초 시간은 1에서 시작하는 것도 혼돈의 함정
입력사항
* 지하 터널 지도의 세로 크기 N, 가로 크기 M은 각각 5 이상 50 이하이다.
* 맨홀 뚜껑의 위치 R, C는 지도의 영역 내부에 존재한다. 또한 맨홀은 언제나 터널 위에 존재한다.
* 탈출 후 소요된 시간 L은 1 이상 20 이하이다. -- 처음 시작 시간이 1이라는 점을 주의 한다.
* 지하 터널 지도에는 반드시 1개 이상의 터널이 있음이 보장된다.
* 터널 구조물의 타입은 총 7개로 0인 지점은 애초에 터널이 없어서 갈 수 없는 지점이다.
출력사항
* 탈주범이 위치할 수 있는 장소의 개수
- 탈주범은 탈주범이 지나온 길 어디에나 있을 수 있다. 즉 방문했던 지점의 개수가 필요
동영상 설명
1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.
소스보기
동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.
더보기
package se.code.모의;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class SWEA_모의_1963_탈주범검거 {
static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder output = new StringBuilder();
static StringTokenizer tokens = null;
static int TC;
static int N;// 세로 크기
static int M;// 가로 크기
static int R;// 맨홀의 세로 위치
static int C;// 맨홀의 가로 위치
static int L;// 탈출한 후 소요된 시간
static int[][] map;
static int answer;
static int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
static boolean[][] pipes = {{},
{true, true, true, true},
{true, false, true, false},
{false, true, false, true},
{true, true, false, false},
{false, true, true, false},
{false, false, true, true},
{true, false, false, true}
};
public static void main(String[] args) throws IOException {
input = new BufferedReader(new StringReader(src));
TC = Integer.parseInt(input.readLine());
for (int t = 1; t <= TC; t++) {
tokens = new StringTokenizer(input.readLine());
N = Integer.parseInt(tokens.nextToken());
M = Integer.parseInt(tokens.nextToken());
R = Integer.parseInt(tokens.nextToken());
C = Integer.parseInt(tokens.nextToken());
L = Integer.parseInt(tokens.nextToken());
map = new int[N][M];
for (int r = 0; r < N; r++) {
tokens = new StringTokenizer(input.readLine(), " ");
for (int c = 0; c < M; c++) {
map[r][c] = Integer.parseInt(tokens.nextToken());
}
}
answer = 0;
bfs();
output.append("#").append(t).append(" ").append(answer).append("\n");
}
System.out.println(output);
}
static void bfs() {
Point start = new Point(R, C, 1);
Queue<Point> q = new LinkedList<>();
boolean[][] visited = new boolean[N][M];
visited[start.row][start.col] = true;
q.offer(start);
while (!q.isEmpty()) {
Point front = q.poll();
if (front.depth > L) {
return;
}
answer++;
for (int d = 0; d < dirs.length; d++) {
// 해당 방향의 이동이 가능한가?
if (pipes[front.ptype][d]) {
int nr = front.row + dirs[d][0];
int nc = front.col + dirs[d][1];
// 안에 있고 미방문이고 파이프라면 이동가능
if (isIn(nr, nc) && !visited[nr][nc] && map[nr][nc] > 0) {
// 해당 방향에 도착할 수 있는가?
int nt = map[nr][nc];
if (pipes[nt][(d + 2) % 4]) {
visited[nr][nc] = true;
q.offer(new Point(nr, nc, front.depth + 1));
}
}
}
}
}
}
static boolean isIn(int row, int col) {
return 0 <= row && row < N && 0 <= col && col < M;
}
static class Point {
int row, col;
int depth;// 이동 시간과 유관
int ptype;// 해당 지점의 파이프 타입
public Point(int row, int col, int depth) {
this.row = row;
this.col = col;
this.depth = depth;
ptype = map[row][col];
}
@Override
public String toString() {
return "[(" + row + "," + col + ", d=" + depth + ", t=" + ptype + "]";
}
}
static String src = "5\r\n" +
"5 6 2 1 3\r\n" +
"0 0 5 3 6 0\r\n" +
"0 0 2 0 2 0\r\n" +
"3 3 1 3 7 0\r\n" +
"0 0 0 0 0 0\r\n" +
"0 0 0 0 0 0\r\n" +
"5 6 2 2 6\r\n" +
"3 0 0 0 0 3\r\n" +
"2 0 0 0 0 6\r\n" +
"1 3 1 1 3 1\r\n" +
"2 0 2 0 0 2\r\n" +
"0 0 4 3 1 1\r\n" +
"10 10 4 3 9\r\n" +
"0 0 0 0 0 0 0 0 0 0\r\n" +
"0 0 0 7 5 0 5 0 0 0\r\n" +
"0 0 3 2 2 6 0 0 0 0\r\n" +
"0 4 7 2 2 2 7 0 0 4\r\n" +
"0 3 0 1 1 2 2 0 0 5\r\n" +
"0 5 6 1 1 1 1 6 2 5\r\n" +
"7 4 1 2 0 0 4 6 0 0\r\n" +
"5 3 1 7 0 2 2 6 5 7\r\n" +
"7 3 2 1 1 7 1 0 2 7\r\n" +
"3 4 0 0 4 0 5 1 0 1\r\n" +
"20 20 13 11 13\r\n" +
"0 0 0 1 4 4 4 0 0 0 0 0 0 0 0 1 2 3 1 0\r\n" +
"0 0 0 0 0 0 0 0 0 0 0 4 2 7 7 2 0 1 1 0\r\n" +
"0 0 0 0 0 0 0 0 0 6 2 4 4 2 0 4 7 0 6 0\r\n" +
"0 0 0 7 5 5 3 0 0 7 5 0 5 6 4 2 6 3 1 5\r\n" +
"0 0 0 1 2 6 3 3 7 0 3 6 2 4 5 6 7 7 5 7\r\n" +
"0 0 0 3 7 6 1 5 3 3 4 5 7 6 0 4 3 3 1 1\r\n" +
"0 1 2 1 5 6 1 6 1 6 5 1 6 0 0 3 4 1 7 6\r\n" +
"0 2 3 2 2 7 3 0 0 3 2 5 2 1 0 6 5 1 6 5\r\n" +
"0 2 5 7 0 7 1 3 3 4 1 3 3 0 2 3 3 2 4 1\r\n" +
"4 0 0 7 2 4 2 2 1 3 1 6 5 5 6 2 5 1 1 6\r\n" +
"5 6 4 0 3 6 5 2 2 6 1 2 0 1 7 5 7 2 2 2\r\n" +
"1 6 3 1 4 4 1 0 3 0 4 2 7 2 0 2 3 6 2 5\r\n" +
"1 5 7 2 1 1 4 4 2 1 0 2 7 1 6 2 6 6 2 2\r\n" +
"3 7 0 6 5 0 4 0 6 6 7 1 3 1 1 1 5 1 6 6\r\n" +
"0 4 0 1 6 2 1 0 7 0 4 2 5 2 7 0 2 7 1 6\r\n" +
"0 7 3 0 1 7 6 2 0 0 4 2 4 1 3 3 7 0 1 3\r\n" +
"0 1 1 4 3 7 4 5 2 2 4 7 4 7 7 4 6 0 1 6\r\n" +
"0 5 2 2 1 4 6 3 7 0 6 3 5 0 0 6 4 4 2 1\r\n" +
"0 1 2 4 5 6 0 2 0 0 5 6 2 4 6 4 7 6 3 7\r\n" +
"7 7 4 2 3 0 0 4 0 0 7 2 7 5 6 1 4 5 5 4\r\n" +
"50 50 20 12 18\r\n" +
"0 0 0 0 0 0 0 0 0 0 0 0 4 5 0 0 0 0 0 4 2 0 5 2 1 5 3 3 0 0 4 0 5 1 7 2 6 0 7 0 0 0 2 0 0 0 0 0 0 0\r\n" +
"6 7 0 0 0 0 0 0 0 0 0 0 4 5 5 3 6 3 0 2 3 3 0 0 5 6 1 5 3 4 7 6 2 2 1 1 6 5 6 4 6 2 0 0 0 0 2 3 1 0\r\n" +
"0 2 6 5 7 6 0 0 0 0 0 0 6 2 0 5 6 2 0 4 1 5 0 0 2 0 7 7 0 6 0 6 2 2 4 1 2 2 1 6 6 6 0 2 2 5 0 6 5 0\r\n" +
"0 0 0 4 7 2 7 3 7 0 0 0 0 6 7 6 5 1 1 1 2 2 1 3 1 2 7 6 1 2 1 2 4 1 6 1 1 7 3 1 6 6 6 1 1 1 7 0 0 0\r\n" +
"0 0 0 5 4 0 6 3 3 7 0 0 0 6 4 3 2 5 3 1 6 1 0 4 1 0 5 7 6 3 1 1 3 6 1 1 6 3 6 7 3 3 6 5 0 7 2 2 4 6\r\n" +
"0 6 0 7 6 0 7 4 0 5 3 0 4 3 2 0 5 7 3 0 1 3 6 7 7 5 1 7 5 2 0 5 3 1 3 7 1 1 1 5 2 5 1 3 6 7 7 6 4 3\r\n" +
"5 2 0 2 6 5 0 5 6 1 6 5 5 1 7 1 2 3 6 5 1 6 7 7 6 4 1 7 5 2 0 1 3 4 6 4 5 7 2 6 5 6 2 5 6 5 6 5 1 6\r\n" +
"1 2 0 7 0 5 5 0 7 6 2 2 1 3 5 5 3 6 3 7 6 4 1 3 1 3 7 0 3 7 0 2 5 6 1 3 4 1 5 1 7 4 1 7 7 0 4 7 5 5\r\n" +
"7 6 0 3 5 1 4 0 5 2 5 0 1 3 5 5 4 4 6 1 6 5 7 6 2 1 6 5 5 3 0 5 7 1 1 3 6 2 2 2 4 5 7 4 5 1 1 0 7 3\r\n" +
"2 5 4 0 3 1 4 5 6 3 7 0 4 5 3 6 4 5 1 7 4 7 3 1 1 7 7 1 1 5 6 4 7 1 2 6 4 1 7 2 7 1 6 0 5 0 0 0 1 0\r\n" +
"3 0 2 5 1 7 1 1 1 6 5 1 3 1 3 1 1 7 1 3 6 5 5 3 1 3 1 6 2 3 2 6 6 1 1 7 5 7 5 7 1 6 0 3 5 1 5 3 0 0\r\n" +
"0 0 3 2 0 1 4 1 4 1 0 7 3 2 2 4 2 4 4 6 1 1 1 7 2 4 7 4 3 6 3 5 1 6 1 3 7 7 2 6 3 2 1 0 4 6 2 6 3 0\r\n" +
"0 0 5 4 7 2 4 6 4 1 6 7 2 2 1 6 2 1 5 4 7 2 2 1 0 7 6 1 7 2 5 7 0 4 1 6 4 0 3 0 0 5 5 0 7 7 0 3 0 0\r\n" +
"0 0 6 4 3 1 3 1 4 7 2 1 2 4 3 4 1 6 2 1 5 1 1 6 0 7 2 7 2 4 7 4 0 3 7 7 3 3 5 2 0 4 3 0 4 2 0 1 3 5\r\n" +
"0 1 0 5 6 4 4 6 5 7 0 6 1 4 5 6 2 1 2 4 4 1 1 2 6 1 6 2 0 3 7 3 0 0 5 1 7 6 6 6 1 3 4 2 1 0 7 0 5 5\r\n" +
"0 7 2 1 4 2 7 3 0 2 1 4 3 5 1 1 1 1 7 1 4 4 1 7 6 0 1 2 0 5 2 0 0 0 5 4 0 3 7 5 3 1 4 1 2 7 2 6 6 4\r\n" +
"0 1 3 0 3 4 6 3 4 2 4 0 7 5 1 1 2 7 1 6 4 2 2 0 5 6 3 3 1 1 0 0 0 3 0 4 5 4 3 1 1 6 1 6 2 0 1 4 7 7\r\n" +
"0 3 0 0 2 6 1 4 7 5 1 4 3 2 5 1 4 3 6 3 0 2 4 5 7 5 6 2 0 5 6 3 6 4 6 2 0 0 6 0 7 2 2 6 0 0 0 0 0 0\r\n" +
"0 6 7 1 6 4 3 6 0 2 6 7 6 2 1 6 6 6 2 0 0 7 3 0 1 1 2 0 0 0 3 1 6 7 5 6 4 1 7 5 2 0 2 6 0 0 0 0 4 0\r\n" +
"0 6 7 7 3 3 0 2 0 1 6 4 1 1 1 6 2 3 3 4 2 3 5 0 5 7 7 6 2 7 2 7 3 1 0 5 6 7 1 6 4 1 5 0 0 0 0 0 0 0\r\n" +
"0 7 3 0 4 3 0 0 6 6 0 5 1 1 1 1 1 6 0 0 7 0 0 0 2 4 3 2 3 3 6 0 0 1 0 2 6 7 3 4 0 3 2 4 0 0 0 0 0 7\r\n" +
"0 0 4 7 2 0 0 0 1 4 2 4 7 7 2 4 2 4 0 5 6 0 0 0 7 0 2 7 4 4 1 6 1 4 2 3 6 2 0 6 5 3 5 0 3 5 6 0 0 1\r\n" +
"0 0 7 4 7 0 3 0 4 4 6 2 4 7 0 5 7 1 3 6 5 6 6 7 3 3 6 6 4 2 0 0 3 0 4 7 2 6 4 0 6 2 4 6 7 1 7 2 7 1\r\n" +
"0 0 2 6 0 0 6 5 0 4 1 2 2 2 2 7 2 1 0 4 6 4 1 0 1 1 2 2 0 4 4 2 0 0 3 0 3 6 2 2 7 6 6 0 4 6 0 2 2 2\r\n" +
"0 0 4 4 7 1 1 1 7 3 7 6 2 3 3 0 5 0 0 6 1 2 6 3 1 7 0 4 7 4 3 6 1 5 1 0 3 7 4 0 3 0 5 6 2 0 0 3 0 5\r\n" +
"0 0 7 3 0 5 4 0 7 4 0 0 4 5 7 1 3 2 3 3 5 3 5 3 5 5 5 5 4 2 3 6 0 3 1 7 2 4 5 3 0 0 5 3 6 0 0 7 3 6\r\n" +
"0 0 3 5 0 0 1 1 1 0 0 0 5 3 5 5 1 2 7 0 4 3 1 6 7 1 5 7 4 4 5 7 0 3 6 3 3 7 7 4 1 3 5 2 0 0 0 7 7 4\r\n" +
"0 0 7 6 3 5 0 7 2 7 7 5 4 0 0 7 0 4 0 0 3 2 3 1 5 7 4 6 0 3 5 5 2 0 6 0 0 0 2 1 1 4 3 6 2 0 5 1 1 6\r\n" +
"0 0 1 0 4 1 0 2 5 0 0 0 6 7 3 7 0 0 0 0 4 3 3 3 0 1 0 0 0 1 5 1 5 4 5 1 7 0 0 5 0 5 6 0 3 2 5 0 3 4\r\n" +
"0 0 0 0 0 4 0 2 3 1 6 6 6 3 5 3 6 0 0 0 4 7 0 6 1 7 1 0 0 5 5 2 5 1 0 1 1 3 3 4 1 4 2 0 6 3 0 0 6 4\r\n" +
"6 4 2 2 0 0 0 3 3 0 0 1 4 0 5 0 2 0 7 0 1 7 7 1 5 7 0 0 0 3 1 5 5 6 0 6 2 6 4 0 7 6 5 1 3 3 7 0 2 5\r\n" +
"0 0 0 7 7 0 0 4 4 3 1 6 1 0 1 3 3 1 4 5 7 3 7 0 0 4 0 0 0 7 3 7 2 2 0 1 5 0 7 5 5 2 5 1 0 2 0 0 3 2\r\n" +
"0 0 0 3 0 0 0 0 1 2 6 7 1 6 7 0 3 5 2 7 3 0 4 5 2 0 0 0 0 2 5 7 3 7 5 6 0 0 2 2 5 4 7 6 4 5 1 4 4 6\r\n" +
"0 4 3 0 0 0 0 3 5 6 3 2 0 3 6 0 6 0 0 1 4 3 6 2 4 7 4 7 1 5 0 4 0 0 2 0 0 0 3 7 6 1 2 5 3 5 2 3 3 3\r\n" +
"0 0 0 1 4 0 0 2 1 0 2 0 0 1 7 3 4 3 3 4 7 0 6 7 4 7 3 1 6 1 7 3 4 4 7 5 2 1 3 7 2 5 2 3 3 2 3 0 1 2\r\n" +
"0 0 0 0 1 1 0 0 5 7 3 6 6 0 0 6 5 4 2 7 0 0 4 5 5 0 5 7 3 3 0 3 5 5 3 6 0 0 3 5 4 0 0 7 5 1 6 0 0 7\r\n" +
"0 0 0 0 5 6 3 1 5 2 0 7 7 7 0 0 1 0 3 6 4 1 6 7 2 1 6 5 2 0 0 7 4 5 0 0 0 0 0 6 6 0 0 5 6 0 2 3 4 5\r\n" +
"0 0 7 1 0 1 6 5 6 0 0 5 4 5 7 1 1 6 5 2 2 0 3 7 4 5 2 6 4 0 0 3 4 0 0 0 0 0 0 7 7 7 7 6 4 3 4 4 0 0\r\n" +
"0 0 0 1 3 0 0 3 7 1 1 0 4 1 4 4 2 6 1 6 2 2 7 4 2 4 1 7 1 6 4 3 3 1 3 4 0 0 3 2 0 2 0 1 3 3 4 7 1 5\r\n" +
"0 0 0 3 4 0 0 2 0 5 5 0 0 1 4 4 0 4 0 1 6 6 4 2 1 0 0 3 7 0 4 3 3 2 3 5 3 5 0 4 0 5 0 3 0 7 7 3 5 6\r\n" +
"0 0 0 7 2 0 0 4 2 2 6 2 2 5 0 5 0 3 4 3 5 5 2 0 4 0 0 5 0 0 4 1 6 4 4 3 4 0 0 5 0 1 1 2 0 7 3 4 0 4\r\n" +
"0 0 1 1 4 4 1 0 0 0 3 5 4 5 4 2 7 4 6 1 6 7 0 3 0 7 1 7 6 6 3 0 5 7 6 6 4 7 3 4 5 0 0 0 0 6 1 1 5 3\r\n" +
"0 0 4 2 5 7 4 4 2 1 2 1 3 4 7 2 7 2 1 6 3 3 0 7 5 6 6 4 5 5 3 3 2 7 5 3 1 4 7 0 0 0 0 0 0 3 1 5 6 5\r\n" +
"0 0 0 4 4 1 0 0 6 0 0 7 5 7 5 1 7 3 6 0 2 4 3 4 7 7 3 0 0 0 1 5 5 0 6 7 7 7 4 4 3 6 3 7 5 0 1 1 0 2\r\n" +
"0 0 0 1 3 4 7 2 5 0 0 4 4 0 5 2 2 0 1 7 0 1 1 3 6 5 2 6 2 7 7 3 6 7 1 3 4 6 7 5 3 7 4 6 0 0 0 4 3 1\r\n" +
"0 0 0 2 1 6 3 5 4 0 0 6 0 0 6 7 0 0 5 2 0 7 7 0 7 0 0 7 7 6 0 0 1 1 0 1 0 1 3 1 0 0 4 7 7 0 0 0 2 6\r\n" +
"0 0 0 2 4 0 6 7 2 4 1 5 6 3 0 0 0 0 4 2 7 1 1 5 2 0 0 7 2 2 3 1 3 5 5 7 7 4 0 3 4 2 3 0 0 4 6 6 0 1\r\n" +
"0 0 0 4 6 1 0 3 6 4 7 3 5 0 0 0 0 0 0 7 0 0 3 6 2 1 0 2 3 4 6 7 5 0 7 0 5 4 5 1 5 0 0 0 0 4 5 3 1 0\r\n" +
"1 3 6 5 5 2 3 7 6 1 0 6 7 3 2 5 6 7 6 6 0 0 7 1 0 5 5 0 3 0 2 0 7 4 5 3 2 5 1 5 3 0 0 0 1 2 0 1 0 0\r\n" +
"1 7 3 0 2 0 7 0 4 6 1 1 5 0 7 0 5 7 7 2 6 0 0 1 0 2 3 3 4 2 7 5 3 7 0 0 4 6 6 6 3 0 0 0 7 7 7 5 7 2";
}