1953. 탈주범 검거

1953. 탈주범 검거

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

DFS입니다.

가장 핵심은 이미 검사한(방문한) 길을 검사하지 않는 것입니다.

하지만 시간이라는 개념이 있기 때문에, 무조건 검사(방문)를 했다고 해서, 검사를 안하면 안됩니다.

새로운 맵을 만들어서, 

해당 길(블록)을 검사한 시간을 적어두고,

현재 검사하려는 시간보다 더 짧은 시간이 블록에 기록되어있으면 검사할 필요가 없고,

현재 시간보다 더 오래된 시간이 블록에 기록되어 있으면 검사를 해야합니다.

짧은 시간일 수록 앞으로 검사할 블록이 많아지기 때문이죠.

2018년 4월 15일 - 다듬지 않은 코드 (소요시간 한시간 정도) import java.util.Scanner; public class Q1953 { static int ySize, xSize, finishTime, position; static int[][] map, visitMap, blocks = { {1, 1, 1, 1},  {1, 1, 0, 0},  {0, 0, 1, 1},  {1, 0, 0, 1},  {0, 1, 0, 1},  {0, 1, 1, 0},  {1, 0, 1, 0}}; static int[] moveY = {-1, 1, 0, 0}, moveX = {0, 0, -1, 1}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int testCase = sc.nextInt(); for (int i = 1; i <= testCase; i++) { ySize = sc.nextInt(); xSize = sc.nextInt(); int nowY = sc.nextInt(); int nowX = sc.nextInt(); finishTime = sc.nextInt(); map = new int[ySize][xSize]; for (int j = 0; j < ySize; j++) { for (int k = 0; k < xSize; k++) { map[j][k] = sc.nextInt()-1; } } visitMap = new int[ySize][xSize]; position = 0; checkMap(nowY, nowX, 1); int result = getChecktedMapNum(); System.out.println("#" + i + " " + result); } } static void checkMap(int y, int x, int time) { if (visitMap[y][x] != 0 && visitMap[y][x] <= time) { return; } visitMap[y][x] = time; int nowBlock = map[y][x]; if (time == finishTime) { return; } //위로 가능 if (blocks[nowBlock][0] == 1 && 0 <= y-1 && map[y-1][x] != -1 && blocks[map[y-1][x]][1] == 1) { checkMap(y-1, x, time+1); } //아래로 가능 if (blocks[nowBlock][1] == 1 && y+1 < ySize && map[y+1][x] != -1 && blocks[map[y+1][x]][0] == 1) { checkMap(y+1, x, time+1); } //좌로 가능 if (blocks[nowBlock][2] == 1 && 0 <= x-1 && map[y][x-1] != -1 && blocks[map[y][x-1]][3] == 1) { checkMap(y, x-1, time+1); } //우로 가능 if (blocks[nowBlock][3] == 1 && x+1 < xSize && map[y][x+1] != -1 && blocks[map[y][x+1]][2] == 1) { checkMap(y, x+1, time+1); } } static int getChecktedMapNum() { int result = 0; for (int i = 0; i < ySize; i++) { for (int j = 0; j < xSize; j++) { if (visitMap[i][j] > 0) { result += 1; } } } return result; } }