2382. 미생물 격리

2382. 미생물 격리

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

어떤 식으로 구현할까 생각하다가 아래와 같은 로직으로 구현했습니다.

1시간 동안

1. 맵을 만든다.

2. 군집을 다음 위치로 이동하고 이동한 위치에 +1;

3. 맵을 처음부터 끝까지 검사하면서 값이 2이상일 경우 (군집이 합쳐질 경우)

해당 위치의 군집을 병합

근데, 군집 병합 과정을 복잡하게 구현해놔서,

디버깅 좀 했어요;;

1. 병합할 군집을 모두 찾아서

미생물의 최대값을 가진 군집을 계산합니다.

2. 해당 군집에 다른 군집의 미생물 수를 더해줍니다.

3. 다른 군집은 0으로 체크하면서 죽여줍니다. (살았는지, 죽었는지 체크를 추가했어요)

(0이기 때문에 다음부터는 쳐다도 안봅니다.)

2018년 4월 13일 - 다듬지 않은 코드 (소요시간 47분) package sw; import java.util.Scanner; public class Q2382 { static int[][] map; static int time, num, mapSize; static int[][] group; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int testCase = sc.nextInt(); for (int i = 1; i <= testCase; i++) { mapSize = sc.nextInt(); // map = new int[mapSize][mapSize]; // // for (int j = 0; j < mapSize; j++) { // for (int k = 0; k < mapSize; k++) { // map[j][k] = -1; //기본 -1 // } // } time = sc.nextInt(); num = sc.nextInt(); group = new int[num][5]; //1. 죽었는지(0) 살았는지(1), y, x, 미생물 수, 방향 for (int j = 0; j < num; j++) { group[j][0] = 1; group[j][1] = sc.nextInt(); group[j][2] = sc.nextInt(); group[j][3] = sc.nextInt(); group[j][4] = sc.nextInt(); } for (int j = 0; j < time; j++) { move(); } //미생물 총합 int result = 0; for (int j = 0; j < num; j++) { if (group[j][0] == 1) { result += group[j][3]; } } System.out.println("#" + i + " "+ result); } } static void move() { map = new int[mapSize][mapSize]; for (int i = 0; i < num; i++) { if (group[i][0] == 1) { int nowY = group[i][1]; int nowX = group[i][2]; int nowDirection = group[i][4]; switch (nowDirection) { //상 case 1: nowY -= 1; if (nowY == 0) { //약품 만났다. group[i][3] /= 2; group[i][4] = 2; } break; //하 case 2: nowY += 1; if (nowY == mapSize-1) { //약품 만났다. group[i][3] /= 2; group[i][4] = 1; } break; //좌 case 3: nowX -= 1; if (nowX == 0) { //약품 만났다. group[i][3] /= 2; group[i][4] = 4; } break; //우 case 4: nowX += 1; if (nowX == mapSize-1) { //약품 만났다. group[i][3] /= 2; group[i][4] = 3; } break; } // System.out.println(nowY + ", " + nowX); map[nowY][nowX] +=1; group[i][1] = nowY; group[i][2] = nowX; } } // showMap(); // showValues(); for (int i = 0; i < mapSize; i++) { for (int j = 0; j < mapSize; j++) { int value = map[i][j]; if (value > 1) { //합쳐진다. // System.out.println(i + ", " + j + " " + value); int[] values = new int[value]; int now = 0; int max = -1; for (int k = 0; k < num; k++) { if (group[k][0] == 1 && group[k][1] == i && group[k][2] == j) { values[now] = k; now += 1; if (max == -1) { max = k; } else if (group[max][3] < group[k][3]) { max = k; } } } //하나로 합치기 for (int k = 0; k < value; k++) { int nowValue = values[k]; if (nowValue != max && group[nowValue][0] == 1) { // System.out.println(nowValue); group[nowValue][0] = 0; //죽었다고 선언 group[max][3] += group[nowValue][3]; //군집 합치기 } } } } } } static void showMap() { for (int i = 0; i < mapSize; i++) { for (int j = 0; j < mapSize; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } System.out.println(); } static void showValues() { for (int i = 0; i < num; i++) { System.out.print((i+1) + " : "); for (int j = 0; j < 5; j++) { System.out.print(group[i][j] + " "); } System.out.println(); } System.out.println(); } }