14502번) 연구소

문제 출처 : https://www.acmicpc.net/problem/14502

이 문제를 처음 본 순간 막막했어요.

그런데, DFS라는 것을 알게 된 순간 쭉쭉 풀어나갔습니다.

오랜만에 플러딩 알고리즘도 사용하기도 했어요.

그런데 포문이 너무 많이 돌아간다는 문제가 있어서, 과연 이 방법이 맞나?라는 의구심을 가지고

코딩을 계속 해보니, 정답이 나오네요;;;;

최대 사이즈가 8이라서 가능한걸로 추측해요.

다차원 배열은 .clone()이 먹히지 않는것을 방금 알았어요;;;;;;;;;;;;;

여태 다차원에서 .clone()를 사용했는데;;;;;;;;;;

2018년 4월 9일 - 다듬지 않은 코드 (소요시간 48분) import java.util.Scanner; public class Q14502 { static int result = 0; static int ySize, xSize; public static void main(String[] args) { Scanner sc = new Scanner(System.in); ySize = sc.nextInt(); xSize = sc.nextInt(); int[][] map = new int[ySize][xSize]; for (int i = 0; i < ySize; i++) { for (int j = 0; j < xSize; j++) { map[i][j] = sc.nextInt(); } } for (int i = 0; i < ySize; i++) { for (int j = 0; j < xSize; j++) { checkMap(1, i, j, map); } } System.out.println(result); } static int[][] finalMap; static void checkMap(int count, int y, int x, int[][] map) { if (map[y][x] == 1 || map[y][x] == 2) { return; } int[][] newMap = copyMap(map); newMap[y][x] = 1; // System.out.println(newMap[y][x] + " / " + map[y][x]); if (count == 3) { finalMap = copyMap(newMap); for (int i = 0; i < ySize; i++) { for (int j = 0; j < xSize; j++) { checkVirus(i, j); } } //검사 // System.out.println(); // for (int i = 0; i < ySize; i++) { // System.out.println(); // for (int j = 0; j < xSize; j++) { // System.out.print(finalMap[i][j] + " "); // } // } int tempResult = 0; for (int i = 0; i < ySize; i++) { for (int j = 0; j < xSize; j++) { if (finalMap[i][j] == 0) { tempResult += 1; } } } // System.out.println(); if (result < tempResult) { result = tempResult; } return; } for (int i = y; i < ySize; i++) { for (int j = 0; j < xSize; j++) { checkMap(count +1, i, j, newMap); } } } static int[][] copyMap(int[][] map) { int[][] newMap = new int[ySize][xSize]; for (int i = 0; i < ySize; i++) { for (int j = 0; j < xSize; j++) { newMap[i][j] = map[i][j]; } } return newMap; } static void checkVirus(int y, int x) { if (finalMap[y][x] != 2) { return; } //상 if (0 <= y-1 && finalMap[y-1][x] == 0) { finalMap[y-1][x] = 2; checkVirus(y-1, x); } //하 if (y+1 < ySize && finalMap[y+1][x] == 0) { finalMap[y+1][x] = 2; checkVirus(y+1, x); } //좌 if (0 <= x-1 && finalMap[y][x-1] == 0) { finalMap[y][x-1] = 2; checkVirus(y, x-1); } //우 if (x+1 < xSize && finalMap[y][x+1] == 0) { finalMap[y][x+1] = 2; checkVirus(y, x+1); } } }

위의 코드 보다는 아래의 코드가 소요 시간이 더 빠릅니다.

벽돌 삽입을 할때, 이전 코드보다 더 효율적으로 구현했어요.

2018년 4월 12일 - 다듬지 않은 코드 (소요시간 20분) import java.util.Scanner; public class Q14502 { static int ySize, xSize, result = 0; static int[][] map, virusMap; public static void main(String[] args) { Scanner sc = new Scanner(System.in); ySize = sc.nextInt(); xSize = sc.nextInt(); map = new int[ySize][xSize]; for (int i = 0; i < ySize; i++) { for (int j = 0; j < xSize; j++) { int value = sc.nextInt(); if (value > 0) { map[i][j] = value; } } } for (int i = 0; i < ySize; i++) { for (int j = 0; j < xSize; j++) { if (map[i][j] == 0) { map[i][j] = 1; setBlock(i, j, 1); map[i][j] = 0; } } } System.out.println(result); } static void setBlock(int y, int x, int count) { if (count == 3) { setVirus(); return; } for (int i = y; i < ySize; i++) { int j; if (i == y) { j = x+1; } else { j = 0; } for (; j < xSize; j++) { if (map[i][j] == 0) { map[i][j] = 1; setBlock(i, j, count+1); map[i][j] = 0; } } } } static void setVirus() { virusMap = new int[ySize][xSize]; for (int i = 0; i < ySize; i++) { for (int j = 0; j < xSize; j++) { virusMap[i][j] = map[i][j]; } } for (int i = 0; i < ySize; i++) { for (int j = 0; j < xSize; j++) { if (virusMap[i][j] == 2) { spreadVirus(i, j); } } } int tempResult = 0; for (int i = 0; i < ySize; i++) { for (int j = 0; j < xSize; j++) { if (virusMap[i][j] == 0) { tempResult += 1; } } } if (result < tempResult) { result = tempResult; } } static void spreadVirus(int y, int x) { virusMap[y][x] = 2; int[] yMove = {-1, 0, 1, 0}; int[] xMove = {0, 1, 0, -1}; for (int i = 0; i < 4; i++) { int tempY = y+yMove[i]; int tempX = x+xMove[i]; if (0 <= tempY && tempY < ySize && 0 <= tempX && tempX < xSize && virusMap[tempY][tempX] == 0) { spreadVirus(tempY, tempX); } } } }