(JAVA) 5653. [모의 SW 역량테스트] 줄기세포배양

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemSolver.do?contestProbId=AWXRJ8EKe48DFAUo

시간 별로 처리하는 로직을 잘 짜면 되는 문제.
– K시간 동안 M*N 크기의 맵에 있는 세포가 증식하는거라서 (K+M+K)*(K+N+K) 크기의 map 배열을 만듦 (최대값)
– 각 cell 별로 상태 (0: 비활성화/1: 활성화/2: 죽음) 배열, 지정 시간 (증식할 때 사용) 배열, 남은 시간 (상태 변경 때 사용) 배열을 만듦
– 매 시간 마다,
* 비활성화 상태에서는 시간을 1씩 줄이고 0이 되면 활성화 상태로 넘어감 (status 0 > 1)
* 활성화 상태에서는 좌/우/상/하 순으로 주변 셀이 비어있는지 확인하고 비어있으면 증식, 비어있지 않은데 현재 시간에 증식한 경우에는 더 큰 세포 값으로 치환, 이외의 경우에는 무시.
이후 시간을 1씩 줄이고 0이 되면 죽음 상태로 넘어감 (status 1>2)
(status 0>1에서는 시간이 >0인 상태로 넘어오고, status 1>2에서는 시간이 0이 되면 status 2로 넘어가기 때문에 문제 없음)
– k 시간이 흐른 후, 상태가 0 혹은 1인 경우의 갯수를 카운트해서 결정

import java.io.*;
import java.util.*;

public class Solution {
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int num = 0; num < numCases; num++) {
				writer.write("#" + String.valueOf(num + 1) + " ");
				
				String[] tmp = reader.readLine().split(" ");
				int numN = Integer.parseInt(tmp[0]); // map 세로 길이 (Y)
				int numM = Integer.parseInt(tmp[1]); // map 가로 길이 (X)
				int numK = Integer.parseInt(tmp[2]); // 배양 시간								
				int numCell = 0;
				
				// 최대 공간을 계산
				int[][] map = new int[numM + 2 * numK][numN + 2 * numK];

				int[] cellX = new int[(numM + 2 * numK)*(numN + 2 * numK)];
				int[] cellY = new int[(numM + 2 * numK)*(numN + 2 * numK)];
				int[] cellStatus = new int[(numM + 2 * numK)*(numN + 2 * numK)];	// 0: 비활성화, 1: 활성화, 2: 죽음
				int[] cellTime = new int[(numM + 2 * numK)*(numN + 2 * numK)];		// 지정 시간
				int[] cellRemainingTime = new int[(numM + 2 * numK)*(numN + 2 * numK)];		// 남은 시간
				
				for (int i = 0; i < numN; i++) { // 세로 길이
					tmp = reader.readLine().split(" ");
					for (int j = 0; j < tmp.length; j++) { // numM (가로 길이)
						int value = Integer.parseInt(tmp[j]);
						
						if (value != 0) { // 세포가 존재
							cellX[numCell] = numK + j;
							cellY[numCell] = numK + i;
							cellTime[numCell] = value;
							cellRemainingTime[numCell] = value;
							
							map[numK + j][numK + i] = value; // map에 값 넣음
							
							numCell++;
						}
					}
				}
				
				// 실제 배양 시도 (1 ~ numK 시간) (i=0일 때 1시간 후의 결과가 나옴)
				for (int i = 0; i < numK; i++) {
					// 이번에 증식된 세포 리스트 (이미 있는 세포와 구분)
					List<String> currentAddedCell = new ArrayList<String>();
					
					int currNumCell = numCell;
					for (int j = 0; j < currNumCell; j++) {
						switch (cellStatus[j]) {
						case 0: // 비활성화
							cellRemainingTime[j]--;
							
							if (cellRemainingTime[j] == 0) {
								cellStatus[j] = 1; // 정해진 시간이 지나면 활성화
								cellRemainingTime[j] = cellTime[j];
							}
								
							break;
						case 1: // 활성화
							int currentX = cellX[j];
							int currentY = cellY[j];
							
							// 좌 증식
							if (map[currentX - 1][currentY] == 0) { // 비어 있는 경우
								map[currentX - 1][currentY] = cellTime[j];
								// 이번에 추가함 (더 큰 수치의 배양 세포 나오면 덮어씌우기) 
								currentAddedCell.add(String.valueOf(currentX - 1) + "/" + String.valueOf(currentY));
								
								cellX[numCell] = currentX - 1;
								cellY[numCell] = currentY;
								cellRemainingTime[numCell] = cellTime[j];
								cellTime[numCell] = cellTime[j];

								numCell++;
							}
							else { // 이미 있는 경우
								// 이번에 추가한 경우 덮어씌울 수 있으면 덮어씌움
								if (currentAddedCell.contains(String.valueOf(currentX - 1) + "/" + String.valueOf(currentY)) == true) {
									if (map[currentX][currentY] > map[currentX - 1][currentY]) {
										map[currentX - 1][currentY] = map[currentX][currentY]; // 최대값 갱신
										for (int k = currNumCell; k < numCell; i++) { // 남은 시간 갱신
											if (cellX[k] == currentX - 1 && cellY[k] == currentY) {
												cellRemainingTime[k] = map[currentX - 1][currentY];
												break;
											}
										}
									}
								}
							}
							// 우 증식
							if (map[currentX + 1][currentY] == 0) { // 비어 있는 경우
								map[currentX + 1][currentY] = cellTime[j];
								// 이번에 추가함 (더 큰 수치의 배양 세포 나오면 덮어씌우기) 
								currentAddedCell.add(String.valueOf(currentX + 1) + "/" + String.valueOf(currentY));
								
								cellX[numCell] = currentX + 1;
								cellY[numCell] = currentY;
								cellRemainingTime[numCell] = cellTime[j];
								cellTime[numCell] = cellTime[j];

								numCell++;
							}
							else { // 이미 있는 경우
								// 이번에 추가한 경우 덮어씌울 수 있으면 덮어씌움
								if (currentAddedCell.contains(String.valueOf(currentX + 1) + "/" + String.valueOf(currentY)) == true) {
									if (map[currentX][currentY] > map[currentX + 1][currentY]) {
										map[currentX + 1][currentY] = map[currentX][currentY]; // 최대값 갱신
										for (int k = currNumCell; k < numCell; i++) { // 남은 시간 갱신
											if (cellX[k] == currentX + 1 && cellY[k] == currentY) {
												cellRemainingTime[k] = map[currentX + 1][currentY];
												break;
											}
										}
									}
								}
							}
							// 상 증식
							if (map[currentX][currentY - 1] == 0) { // 비어 있는 경우
								map[currentX][currentY - 1] = cellTime[j];
								// 이번에 추가함 (더 큰 수치의 배양 세포 나오면 덮어씌우기) 
								currentAddedCell.add(String.valueOf(currentX) + "/" + String.valueOf(currentY - 1));
								
								cellX[numCell] = currentX;
								cellY[numCell] = currentY - 1;
								cellRemainingTime[numCell] = cellTime[j];
								cellTime[numCell] = cellTime[j];

								numCell++;
							}
							else { // 이미 있는 경우
								// 이번에 추가한 경우 덮어씌울 수 있으면 덮어씌움
								if (currentAddedCell.contains(String.valueOf(currentX) + "/" + String.valueOf(currentY - 1)) == true) {
									if (map[currentX][currentY] > map[currentX][currentY - 1]) {
										map[currentX][currentY - 1] = map[currentX][currentY]; // 최대값 갱신
										for (int k = currNumCell; k < numCell; i++) { // 남은 시간 갱신
											if (cellX[k] == currentX && cellY[k] == currentY - 1) {
												cellRemainingTime[k] = map[currentX][currentY - 1];
												break;
											}
										}
									}
								}
							}
							// 하 증식
							if (map[currentX][currentY + 1] == 0) { // 비어 있는 경우
								map[currentX][currentY + 1] = cellTime[j];
								// 이번에 추가함 (더 큰 수치의 배양 세포 나오면 덮어씌우기) 
								currentAddedCell.add(String.valueOf(currentX) + "/" + String.valueOf(currentY + 1));
								
								cellX[numCell] = currentX;
								cellY[numCell] = currentY + 1;
								cellRemainingTime[numCell] = cellTime[j];
								cellTime[numCell] = cellTime[j];

								numCell++;
							}
							else { // 이미 있는 경우
								// 이번에 추가한 경우 덮어씌울 수 있으면 덮어씌움
								if (currentAddedCell.contains(String.valueOf(currentX) + "/" + String.valueOf(currentY + 1)) == true) {
									if (map[currentX][currentY] > map[currentX][currentY + 1]) {
										map[currentX][currentY + 1] = map[currentX][currentY]; // 최대값 갱신
										for (int k = currNumCell; k < numCell; i++) { // 남은 시간 갱신
											if (cellX[k] == currentX && cellY[k] == currentY + 1) {
												cellRemainingTime[k] = map[currentX][currentY + 1];
												break;
											}
										}
									}
								}
							}
							
							// 남은 시간 줄임
							cellRemainingTime[j]--;
							
							if (cellRemainingTime[j] == 0) {
								cellStatus[j] = 2; // 정해진 시간이 지나면 죽음
							}
							break;
						//case 2: // 죽음 
						//	break;
						}
					}
				}
				
				int answer = 0;
				for (int i = 0; i < numCell; i++) {
					if (cellStatus[i] != 2)
						answer++;
				}
				writer.write(answer + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

(JAVA) 5650. [모의 SW 역량테스트] 핀볼 게임

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo

솔직히 한 번에 문제를 어떻게 풀어야 할지 구상이 안 되서 엄청 복잡하게 짜다가 갈아엎고 단순화해서 구현함. (그래도 소스는 복잡해 보임)
– 처음에 map을 만들 때, 블랙홀과 웜홀들 (웜홀 별로)의 위치를 기록함
– 경우의 수는 NXN의 위치, 상하좌우의 방향 (4가지)해서 4*N2 가지의 경우가 성립한다.
(단, 웜홀, 블랙홀, 특수 블록들은 시작 위치가 될 수 없으므로 제외)
– 현재 방향은 윗 방향/아랫 방향/왼쪽 방향/오른쪽 방향 총 4가지 이고
각 방향에서 가장 edge에 (순서대로 맨 윗줄, 맨 아랫줄, 맨 왼쪽 줄, 맨 오른쪽 줄) 있는 경우와 그 외의 경우로 크게 나눴다.
edge에 있는 경우는 각 블록 별로 몇 번 부딪히고 방향은 어디로 바뀌는지 미리 계산하고 (부딪히고 돌아오는 것으로 보고 위치는 수정하지 않음) / 이외의 경우는 블록에 따라 원하는 방향으로 가지 못하는 경우 (부딪히고 방향 바뀜), 원하는 방향으로 가는 경우 (부딪히고 방향 바뀜 or 위치만 이동)로 나누어 구현. (주석은 귀찮아서 윗 방향일 때만 full로 달았음)
– 아무래도 현재 위치/현재 블록/다음 블록 과 같이 조건의 조합이 많아서 좀 복잡했는데, 차분하게 디버깅하면서 짜니 결국은 원하는 답이 나옴.

import java.io.*;
import java.util.*;

public class Solution {
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int num = 0; num < numCases; num++) {
				writer.write("#" + String.valueOf(num + 1) + " ");
				int numN = Integer.parseInt(reader.readLine()); // map 크기
				
				int[][] map = new int[numN][numN];
				Map<Integer, List<String>> wormhole = new HashMap<Integer, List<String>>(); // 웜홀 (6~10)
				List<String> blackhole = new ArrayList<String>();		// 블랙홀
				
				// 맵 만들기
				for (int i = 0; i < numN; i++) {
					String[] tmp = reader.readLine().split(" ");
					
					for (int j = 0; j < tmp.length; j++) {
						map[j][i] = Integer.parseInt(tmp[j]);

						int tmp_ = map[j][i];
						
						if (tmp_ >= 6 || tmp_ == -1) {
							switch (tmp_) {
							case -1: // 블랙홀
								blackhole.add(j + "/" + i);
								break;
							case 6:  // 웜홀 6
							case 7:  // 웜홀 7
							case 8:  // 웜홀 8
							case 9:  // 웜홀 9
							case 10: // 웜홀 10
								if (wormhole.containsKey(tmp_) == false)
									wormhole.put(tmp_, new ArrayList<String>());
								
								wormhole.get(tmp_).add(j + "/" + i);
								break;
							}
						}
					}
				}
				
				// 실제 진행
				int startX = 0, startY = 0;
				int X = 0, Y = 0, direction = 0; // 현재 X, Y, 방향
				int maxScore = 0;
				
				for (int i = 0; i < numN; i++) { 
					for (int j = 0; j < numN; j++) {
						// 블록, 웜홀, 블랙홀: 시작점이 될 수 없음
						if (map[i][j] != 0)
							continue;
						
						startX = i; // 시작점 
						startY = j; // 끝점
						
						// 방향별 / 0: 위, 1: 아래, 2: 왼쪽, 3: 오른쪽 
						for (int k = 0; k < 4; k++) {
							X = startX; // 초기화 (X)
							Y = startY; // 초기화 (Y)
							direction = k; // 초기화 (방향)
							int score = 0; // 초기화 (점수)
							
							boolean isFirst = true;

							// 조건이 될 때까지 진행
							while (true) {
								if (isFirst == true) // 처음인 경우 (최초는 X==startX 이고 Y==startY이므로 한 번 진행한 후 확인)
									isFirst = false;
								else if ((X == startX && Y == startY)) // 시작 위치로 돌아오는 경우 (블랙홀은 아래 이동 후 루틴에서 처리)
									break;
								
								int currentBlock = map[X][Y]; // 현재 블록

								// 실제 이동 수행
								switch (direction) {
								case 0: // 위 
									if (Y == 0) { // 맨 윗줄
										if (currentBlock == 0) { // 아무 것도 없는 블록: 벽에 부딪히고 나서 아래로
											score++;
											direction = 1; 
										}
										else if (currentBlock == 1) { // 좌하 직각삼각형:벽에 부딪히고, 블록에 부딪히고 오른쪽으로
											score += 2;
											direction = 3;
										}
										else if (currentBlock == 4) { // 우하 직각삼각형:벽에 부딪히고, 블록에 부딪히고 왼쪽으로
											score += 2;
											direction = 2;
										}
										else if (currentBlock == 2) { // 좌상 직각삼각형: 블록에 부딪히고 오른쪽으로
											score++;
											direction = 3;
										}
										else if (currentBlock == 3) { // 우상 직각삼각형: 블록에 부딪히고 왼쪽으로
											score++;
											direction = 2;
										} // 웜홀: 아무 것도 없는 경우와 동일 
										else if (currentBlock >= 6 && currentBlock <= 10) {
											score++; 
											direction = 1; 
										}
									}
									else { // 이외의 경우
										if (currentBlock == 2) { // 위로 갈 수 없으므로, 부딪힌 후 오른쪽으로 변경되는 것 반영
											score++;
											direction = 3;
										}
										else if (currentBlock == 3) { // 위로 갈 수 없으므로, 부딪힌 후 왼쪽으로 변경되는 것 반영
											score++;
											direction = 2;
										}
										else { // 위로 갈 수 있는 경우 다음 블록 체크
											int nextMap = map[X][Y-1];
											if (nextMap == 1 || nextMap == 4 || nextMap == 5) { // 위로 못 올라오는 경우, 부딪히고 방향 변경
												score++;
												direction = 1;
											}
											else if (nextMap == 2) { // 위로 올라와서 부딪히고 오른쪽으로 향함
												score++;
												direction = 3;
												Y--;
											}
											else if (nextMap == 3) { // 위로 올라와서 부딪히고 왼쪽으로 향함
												score++;
												direction = 2;
												Y--;
											}
											else // 일반블럭, 웜홀, 블랙홀은 위치만 이동 (웜홀, 블랙홀은 차후 처리) 
												Y--;
										}
									}
									break;
								case 1: // 아래 
									if (Y == numN - 1) { // 맨 아랫줄
										if (currentBlock == 0) {
											score++;
											direction = 0; 
										}
										else if (currentBlock == 2) {
											score += 2;
											direction = 3;
										}
										else if (currentBlock == 3) {
											score += 2;
											direction = 2;
										}
										else if (currentBlock == 1) { // 위에 부딪혀서 내려온 경우 
											score++;
											direction = 3;
										}
										else if (currentBlock == 4) { // 위에 부딪혀서 내려온 경우 
											score++;
											direction = 2;											
										}
										else if (currentBlock >= 6 && currentBlock <= 10) {
											score++;
											direction = 0; 
										}
									}
									else { // 이외의 경우
										if (currentBlock == 1) {
											score++;
											direction = 3;
										}
										else if (currentBlock == 4) {
											score++;
											direction = 2;
										}
										else {
											int nextMap = map[X][Y+1];
											if (nextMap == 2 || nextMap == 3 || nextMap == 5) { // 아래로 못 내려가는 경우
												score++;
												direction = 0;
											}
											else if (nextMap == 1) {
												score++;
												direction = 3;
												Y++;
											}
											else if (nextMap == 4) {
												score++;
												direction = 2;
												Y++;
											}
											else
												Y++;
										}
									}
									break;
								case 2: // 왼쪽 
									if (X == 0) { // 맨 왼쪽줄
										if (currentBlock == 0) {
											score++;
											direction = 3; 
										}
										else if (currentBlock == 3) {
											score += 2;
											direction = 1;
										}
										else if (currentBlock == 4) {
											score += 2;
											direction = 0;
										}
										else if (currentBlock == 1) {
											score++;
											direction = 0;
										}
										else if (currentBlock == 2) {
											score++;
											direction = 1;
										}
										else if (currentBlock >= 6 && currentBlock <= 10) {
											score++;
											direction = 3; 
										}
									}
									else { // 이외의 경우
										if (currentBlock == 1) {
											score++;
											direction = 0;
										}
										else if (currentBlock == 2) {
											score++;
											direction = 1;
										}
										else {
											int nextMap = map[X-1][Y];
											if (nextMap == 3 || nextMap == 4 || nextMap == 5) { // 왼쪽으로 못 가는 경우
												score++;
												direction = 3;
											}
											else if (nextMap == 1) {
												score++;
												direction = 0;
												X--;
											}
											else if (nextMap == 2) {
												score++;
												direction = 1;
												X--;
											}
											else
												X--;
										}
									}
									break;
								case 3: // 오른쪽
									if (X == numN - 1) { // 맨 오른쪽줄
										if (currentBlock == 0) {
											score++;
											direction = 2; 
										}
										else if (currentBlock == 1) {
											score += 2;
											direction = 0;
										}
										else if (currentBlock == 2) {
											score += 2;
											direction = 1;
										}	
										else if (currentBlock == 3) {
											score++;
											direction = 1;
										}
										else if (currentBlock == 4) {
											score++;
											direction = 0;
										}
										else if (currentBlock >= 6 && currentBlock <= 10) {
											score++;
											direction = 2; 
										}
									}
									else { // 이외의 경우
										if (currentBlock == 3) { 
											score++;
											direction = 1;
										}
										else if (currentBlock == 4) {
											score++;
											direction = 0;
										}
										else {
											int nextMap = map[X+1][Y];
											if (nextMap == 1 || nextMap == 2 || nextMap == 5) { // 오른쪽으로 못 가는 경우
												score++;
												direction = 2;
											}
											else if (nextMap == 3) {
												score++;
												direction = 1;
												X++;
											}
											else if (nextMap == 4) {
												score++;
												direction = 0;
												X++;
											}
											else
												X++;
										}
									}
									break;
								}
									
								// 웜홀 처리
								if (map[X][Y] >= 6 && map[X][Y] <= 10) {
									List<String> wormholePair = wormhole.get(map[X][Y]);
									for (String pos: wormholePair) {
										if (pos.equals(X + "/" + Y) == false) { // 지금 웜홀과 다른 웜홀을 발견하면 그 곳으로 이동
											String[] tmp__ = pos.split("/");
											X = Integer.parseInt(tmp__[0]);
											Y = Integer.parseInt(tmp__[1]);
											break;												
										}
									}
								}
								// 블랙홀 처리 
								else if (map[X][Y] == -1)
									break;
							}
							
							if (maxScore < score) {
								maxScore = score;
							}
						}						
					}					
				}	
				
				writer.write(maxScore + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

(JAVA) 5648. [모의 SW 역량테스트] 원자 소멸 시뮬레이션

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRFInKex8DFAUo

완전 명쾌하게 풀었다고 하긴 좀 거시기하긴 한데……
나름대로 머리를 굴려서 (?) 풀긴 풀었음.
– 1초마다 1씩 이동을 한다고 했는데, 거리가 1일 경우 중간지점에서 충돌하는 경우도 있어서 0.5초 단위로 계산하게 함 (이로 인해 루프 횟수가 2배로 늘어나는 게 함정…)
– 정수로 계산하게 하려고 거리 정보를 2배씩 곱함. 즉 0.5초마다 1씩 움직이는걸로 (=1초마다 2씩 움직임) 계산을 고침.
– 매 0.5초마다 원소를 이동시킨 후, 각 원소의 위치를 List에 투입. 이후 각 원소의 위치가 List에 이미 있는지 확인 후, 이미 있으면 해당하는 원소들을 모두 폭발 처리 (원소 에너지는 0으로, 원래 에너지는 총 에너지에 합산)
– 20번 (=10초)마다 충돌 가능성이 없는 원소를 제외하는 로직 추가 (20번마다 하는 이유는 제외하는 로직의 시간이 오래 걸리기 때문에.. 하지만 이 로직이 아예 없으면 최대 거리 기준으로 루프가 돌아가기 때문에 또 오래 걸린다는 문제가 있으므로 적당한 밸런스 조절)

import java.io.*;
import java.util.*;

public class Solution {
	public static final int xBound = 2000, yBound = 2000;
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int num = 0; num < numCases; num++) {
				writer.write("#" + String.valueOf(num + 1) + " ");

				int numN = Integer.parseInt(reader.readLine()); // 원자 수 
				
				int[] xAtom = new int[numN]; // 원자 X 위치 
				int[] yAtom = new int[numN]; // 원자 Y 위치
				int[] directionAtom = new int[numN]; // 원자 이동방향
				int[] energyAtom = new int[numN]; // 원자 에너지
				
				for (int i = 0; i < numN; i++) {
					String[] tmp = reader.readLine().split(" ");
					
					xAtom[i] = 2 * Integer.parseInt(tmp[0]); // -1000~1000을 -2000~2000으로 스케일링 (0.5초 당 1씩 움직이는 걸로 환산)
					yAtom[i] = 2 * Integer.parseInt(tmp[1]); // -1000~1000을 -2000~2000으로 스케일링 (0.5초 당 1씩 움직이는 걸로 환산) 
					directionAtom[i] = Integer.parseInt(tmp[2]); // 0: 상, 1: 하, 2: 좌, 3: 우
					energyAtom[i] = Integer.parseInt(tmp[3]);
				}
				
				int answer = 0;
				
				// 8000: 2*(2000-(-2000)), 즉 가장 먼 거리 기준으로 계산
				for (int i = 0; i < 4 * xBound; i++) {
					boolean allReachedEnd = true;

					Map<String, Integer> isFound = new HashMap<String, Integer>();
					
					// 충돌 가능성 없으면 미리 배제 
					if (i % 20 == 0) { // 20번에 한 번 빈도로만 수행 (시간이 오래 걸리기 때문에)
						for (int j = 0; j < numN; j++) {
							if (energyAtom[j] == 0) // 이미 폭발한 경우 확인하지 않음
								continue;
	
							boolean toEscape = false;
	
							for (int k = 0; k < numN; k++) {
								if (j == k) // 같은 경우는 계산하지 않음 
									continue;
															
								switch (directionAtom[j]) {
								case 0: // 상 
									if (yAtom[j] < yAtom[k]) { // 더 위에  
										if (directionAtom[k] == 1) // 아래로 내려오는 원소가 있을 경우
											toEscape = true;
										else if (directionAtom[k] == 2 || directionAtom[k] == 3) { // 좌나 우로 이동하고,
											if (yAtom[k] - yAtom[j] == Math.abs(xAtom[k] - xAtom[j])) // 만날 가능성이 있을 때
												toEscape = true;
										}
									}
									break;
								case 1: // 하
									if (yAtom[j] > yAtom[k]) { // 더 아래에  
										if (directionAtom[k] == 0) // 아래로 내려오는 원소가 있을 경우
											toEscape = true;
										else if (directionAtom[k] == 2 || directionAtom[k] == 3) { // 좌나 우로 이동하고,
											if (yAtom[j] - yAtom[k] == Math.abs(xAtom[k] - xAtom[j])) // 만날 가능성이 있을 때
												toEscape = true;
										}
									}
									break;
								case 2: // 좌
									if (xAtom[j] > xAtom[k]) { // 더 왼쪽에  
										if (directionAtom[k] == 3) // 오른쪽으로 오는 원소가 있을 경우
											toEscape = true;
										else if (directionAtom[k] == 0 || directionAtom[k] == 1) { // 좌나 우로 이동하고,
											if (xAtom[j] - xAtom[k] == Math.abs(yAtom[k] - yAtom[j])) // 만날 가능성이 있을 때
												toEscape = true;
										}
									}
									break;
								case 3: // 우 
									if (xAtom[j] < xAtom[k]) { // 더 오른쪽에  
										if (directionAtom[k] == 2) // 왼쪽으로 오는 원소가 있을 경우
											toEscape = true;
										else if (directionAtom[k] == 0 || directionAtom[k] == 1) { // 좌나 우로 이동하고,
											if (xAtom[k] - xAtom[j] == Math.abs(yAtom[k] - yAtom[j])) // 만날 가능성이 있을 때
												toEscape = true;
										}
									}
									break;
								}
								
								// 충돌 가능성이 있으면 더 이상 진행하지 않음
								if (toEscape == true)
									break;
							}
							// 충돌 가능성이 없으면 에너지를 0으로 처리 (넣을 일이 없음)
							if (toEscape == false)
								energyAtom[j] = 0;
						}
					}
					
					// 각 원소 이동시킴
					for (int j = 0; j < numN; j++) {
						if (energyAtom[j] == 0) // 이미 폭발한 경우 확인하지 않음
							continue;

						allReachedEnd = false;
						
						switch (directionAtom[j]) {
						case 0: // 상 
							yAtom[j]++;
							break;
						case 1: // 하
							yAtom[j]--;
							break;
						case 2: // 좌
							xAtom[j]--;
							break;
						case 3: // 우 
							xAtom[j]++;
							break;
						}
						
						String key = xAtom[j] + "/" + yAtom[j];
						// 이미 겹치는 위치가 있음
						if (isFound.containsKey(key) == true) {
							int firstAtom = isFound.get(key);
							if (energyAtom[firstAtom] != 0) {
								answer += energyAtom[firstAtom];
								energyAtom[firstAtom] = 0;
							}
							
							answer += energyAtom[j];
							energyAtom[j] = 0;								
						}
						else
							isFound.put(key, j);
					}
					
					// 모든 원소가 더 이상 이동안될 경우 중단 
					if (allReachedEnd == true)
						break;
				}
				
				writer.write(answer + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

(JAVA) 5644. [모의 SW 역량테스트] 무선 충전

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo

경우의 수 나누는 훈련을 하고 있는거 같다 (…)
– 0 (처음에 안 움직일 때)~ M (주어진 시간)까지 해서 M+1번 정보를 업데이트 해야됨.
– 0일 때 빼고는 이동 정보를 업데이트하고, 이후 사람A과 B가 접근할 수 있는 BC들의 목록을 정함
– 둘 다 접근할 수 있는 BC가 1개 이상이면 겹칠 가능성이 있으므로 모든 경우의 수를 계산하고, 한 명이라도 접근할 수 있는 BC가 0개인 경우 겹칠 일이 없으므로 파워가 가장 센 BC 선택

import java.io.*;
import java.util.*;

public class Solution {	
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int num = 0; num < numCases; num++) {
				writer.write("#" + String.valueOf(num + 1) + " ");

				// 기본 A, B 위치 
				int xUserA = 1, yUserA = 1;
				int xUserB = 10, yUserB = 10;

				String[] tmp = reader.readLine().split(" ");
				int numM = Integer.parseInt(tmp[0]); // 총 이동 시간
				int numA = Integer.parseInt(tmp[1]); // BC의 갯수
								
				// 사용자 A 이동 정보 (0: 이동 안함, 1: 상, 2: 우, 3: 하, 4: 좌)
				String[] tmp_ = reader.readLine().split(" ");
				int[] userA = new int[tmp_.length]; // 사용자 A의 이동 정보
				for (int i = 0; i < tmp_.length; i++)
					userA[i] = Integer.parseInt(tmp_[i]);
				
				// 사용자 B 이동 정보 (0: 이동 안함, 1: 상, 2: 우, 3: 하, 4: 좌)
				tmp_ = reader.readLine().split(" ");
				int[] userB = new int[tmp_.length]; // 사용자 B의 이동 정보
				for (int i = 0; i < tmp_.length; i++)
					userB[i] = Integer.parseInt(tmp_[i]);

				// BC 정보
				int[] xBC = new int[numA]; // 좌표 (X)
				int[] yBC = new int[numA]; // 좌표 (Y)
				int[] cBC = new int[numA]; // 충전 범위
				int[] pBC = new int[numA]; // 처리량
				
				for (int i = 0; i < numA; i++) {
					String[] tmp__ = reader.readLine().split(" ");
					
					xBC[i] = Integer.parseInt(tmp__[0]);
					yBC[i] = Integer.parseInt(tmp__[1]);
					cBC[i] = Integer.parseInt(tmp__[2]);
					pBC[i] = Integer.parseInt(tmp__[3]);
				}

				// 실제 최대 충전량 계산 
				int answer = 0;
				
				// -1: 움직이기 전, 0~numM-1: 움직이는 중 (0~numM 을 -1~numM-1 로 환산)
				for (int i = -1; i < numM; i++) {
//					// 움직이는 경우 (i == -1이면 이동할 필요가 없음)
					if (i != -1) {
						switch (userA[i]) {
						case 1: // 상 
							yUserA--;
							break;
						case 2: // 우
							xUserA++;
							break;
						case 3: // 하
							yUserA++;
							break;
						case 4: // 좌
							xUserA--;
							break;
						}
						
						switch (userB[i]) {
						case 1: // 상 
							yUserB--;
							break;
						case 2: // 우 
							xUserB++;
							break;
						case 3: // 하 
							yUserB++;
							break;
						case 4: // 좌
							xUserB--;
							break;
						}
					}
					
					// 해당 시간에 사용자 A, B가 도달 가능한 BC 목록
					List<Integer> BCForUserA = new ArrayList<Integer>();
					List<Integer> BCForUserB = new ArrayList<Integer>();
					
					for (int j = 0; j < numA; j++) {
						int distanceA = Math.abs(xUserA - xBC[j]) + Math.abs(yUserA - yBC[j]);
						int distanceB = Math.abs(xUserB - xBC[j]) + Math.abs(yUserB - yBC[j]);
						
						if (distanceA <= cBC[j])
							BCForUserA.add(j);
						if (distanceB <= cBC[j])
							BCForUserB.add(j);
					}
					
					// 각 시간 별 최대값 구함 
					int maxValue = 0;
					
					if (BCForUserA.size() >= 1 && BCForUserB.size() >= 1) { // 둘 다 경우의 수가 1 이상이면 비교 필요				
						for (int caseA: BCForUserA) {
							for (int caseB: BCForUserB) {
								if (caseA == caseB) { // 같은 경우 절반씩 나눠가짐
									if (maxValue < 0.5 * (pBC[caseA] + pBC[caseB]))
										maxValue = (int) (0.5 * (pBC[caseA] + pBC[caseB]));
								}
								else { // 다른 경우 각자의 최대값 적용
									if (maxValue < pBC[caseA] + pBC[caseB])
										maxValue = pBC[caseA] + pBC[caseB];								
								}
							}						
						}
					}
					else { // 둘 중 한 쪽 이상이 size() == 0이면 한쪽만 계산
						if (BCForUserA.size() == 0 && BCForUserB.size() == 0) // 둘 다 0
							continue;
						else if (BCForUserA.size() == 0) { // B만 경우의 수가 있음
							for (int caseB: BCForUserB) {
								if (maxValue < pBC[caseB]) 
									maxValue = pBC[caseB];
							}
						}
						else if (BCForUserB.size() == 0) { // A만 경우의 수가 있음
							for (int caseA: BCForUserA) {
								if (maxValue < pBC[caseA]) 
									maxValue = pBC[caseA];
							}							
						}							
					}
					
					answer += maxValue;
				}
				
				writer.write(answer + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

(Java) 4014. [모의 SW 역량테스트] 활주로 건설

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH

– 가로/세로의 경우 로직은 기본적으로 동일하고 2차원 map array에서 순회하는 방향만 다름.
– 각 줄의 경우 (가로/세로) 높이/길이 그룹화를 시킴. (높이 차이가 1이 넘는 경우는 미리 필터링)
– 그룹화된 데이터를 기반으로, 높아질 때는 설치할 수 없을 때 (기존 위치) 필터링함. 낮아질 때는 설치할 수 없을 때 (현재 위치) 필터링하고 현재 위치의 길이를 K (경사로 폭)만큼 감소 (경사로를 두 개 설치해야 할 때 확인 필요).
– 필터링이 안 된 경우에만 가능한 갯수로 카운트

import java.io.*;
import java.util.*;

public class Solution {	
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int num = 0; num < numCases; num++) {
				writer.write("#" + String.valueOf(num + 1) + " ");
				
				String[] tmp = reader.readLine().split(" ");
				int numN = Integer.parseInt(tmp[0]); // 맵 크기 
				int numX = Integer.parseInt(tmp[1]); // 경사로 폭
				
				// Map 생성
				int[][] map = new int[numN][numN];
				for (int i = 0; i < numN; i++) {
					String[] tmp_ = reader.readLine().split(" ");
					
					for (int j = 0; j < tmp_.length; j++)
						map[j][i] = Integer.parseInt(tmp_[j]);
				}
				
				int answer = 0;
				
				// 가로 처리
				for (int i = 0; i < numN; i++) {
					boolean available = true;
					int currentHeight = 0; // 현재 높이
					int currentCount = 0;  // 현재 높이가 이어지는 갯수
					
					Queue<Integer> heightList = new LinkedList<Integer>(); // 높이 목록
					Queue<Integer> countList = new LinkedList<Integer>();  // 갯수 목록
					
					// 최초값 처리
					currentHeight = map[0][i];
					currentCount++;
					
					// 높이/길이 그룹화
					for (int j = 1; j < numN; j++) {
						if (map[j][i] == currentHeight) // 높이가 같은 경우
							currentCount++;
						else {	// 높이가 달라지는 경우
							if (map[j][i] == currentHeight + 1 || map[j][i] == currentHeight - 1) { // 1 차이 나는 경우							
								heightList.add(currentHeight);
								countList.add(currentCount);
								
								currentHeight = map[j][i];
								currentCount = 1;
							}
							else { // 높이 차이가 1이 아닌 경우 아예 불가능
								available = false;
								break;
							}
						}
					}
					
					// 애초에 불가능한 경우 진행하지 않음
					if (available == false)
						continue;
					
					// 마지막 정보도 투입
					heightList.add(currentHeight);
					countList.add(currentCount);
					
					// 높이가 하나만 있는 경우 
					if (heightList.size() == 1) {
						answer++;
						continue;
					}

					int prevHeight = 0;
					int prevCount = 0; 

					currentHeight = heightList.poll();
					currentCount = countList.poll();
					
					while (heightList.size() > 0) {
						prevHeight = currentHeight;
						prevCount = currentCount;
						
						currentHeight = heightList.poll();
						currentCount = countList.poll();
						
						if (prevHeight < currentHeight) { // 현재  높이가 1 더 높은 경우
							if (prevCount < numX) { // 낮은 쪽 (현재) 폭이 좁을 경우
								available = false;
								break;
							}
						}
						if (prevHeight > currentHeight) { // 현재 높이가 1 더 낮은 경우
							if (currentCount < numX) { // 낮은 쪽 (현재) 폭이 좁을 경우
								available = false;
								break;
							}
							
							currentCount -= numX; // 높->낮(현재)->높이 될 때 낮은 위치의 길이가 두 경사로를 설치할 수 있는지 체크하기 위함 
						}
					}

					if (available == true)
						answer++;
				}
				
				// 세로 처리 
				for (int i = 0; i < numN; i++) {
					boolean available = true;
					int currentHeight = 0; // 현재 높이
					int currentCount = 0;  // 현재 높이가 이어지는 갯수
					
					Queue<Integer> heightList = new LinkedList<Integer>(); // 높이 목록
					Queue<Integer> countList = new LinkedList<Integer>();  // 갯수 목록
					
					// 최초값 처리
					currentHeight = map[i][0];
					currentCount++;
					
					for (int j = 1; j < numN; j++) {
						if (map[i][j] == currentHeight) // 높이가 같은 경우
							currentCount++;
						else {	// 높이가 달라지는 경우
							if (map[i][j] == currentHeight + 1 || map[i][j] == currentHeight - 1) { // 1 차이 나는 경우
								heightList.add(currentHeight);
								countList.add(currentCount);
								
								currentHeight = map[i][j];
								currentCount = 1;
							}
							else { // 높이 차이가 1이 아닌 경우 아예 불가능
								available = false;
								break;
							}
						}
					}
					
					// 애초에 불가능한 경우 진행하지 않음
					if (available == false)
						continue;

					// 마지막 정보도 투입
					heightList.add(currentHeight);
					countList.add(currentCount);
					
					// 높이가 하나만 있는 경우 
					if (heightList.size() == 1) {
						answer++;
						continue;
					}

					int prevHeight = 0;
					int prevCount = 0; 

					currentHeight = heightList.poll();
					currentCount = countList.poll();
					
					while (heightList.size() > 0) {
						prevHeight = currentHeight;
						prevCount = currentCount;
						
						currentHeight = heightList.poll();
						currentCount = countList.poll();
						
						if (prevHeight < currentHeight) { // 현재 높이가 1 더 높은 경우
							if (prevCount < numX) { // 낮은 쪽 (현재) 폭이 좁을 경우
								available = false;
								break;
							}
						}
						else if (prevHeight > currentHeight) { // 현재 높이가 1 더 낮은 경우
							if (currentCount < numX) { // 낮은 쪽 (현재) 폭이 좁을 경우
								available = false;
								break;
							}
							
							currentCount -= numX; // 높->낮(현재)->높이 될 때 낮은 위치의 길이가 두 경사로를 설치할 수 있는지 체크하기 위함 
						}
					}
										
					if (available == true) 
						answer++;
				}
				
				writer.write(answer + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

(JAVA) 4013. [모의 SW 역량테스트] 특이한 자석

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeV9sKkcoDFAVH&

이론적으로는 BFS로 구성할 수 있을 것 같긴 한데… 그냥 나름대로 풀이함.
– 각 자석 별로 arrowIdx (화살표 부분), leftIdx (왼쪽 부분), rightIdx (오른쪽 부분)가 있음.
회전할 때 세 값을 모두 업데이트 해야됨 (주의점: 반시계 방향이면 arrowIdx 가 증가하고, 시계 방향이면 arrowIdx가 감소함)
– 최초로 회전하는 자석 (trigger)을 기준으로 오른쪽 방향으로 연쇄적 처리, 왼쪽 방향으로 연쇄적 처리함
(최초 회전한 자석 기준으로 오른쪽 자석이 영향을 받고, 그 오른쪽 자석이 영향을 받고… 이런 방식.
역으로 왼쪽 좌석이 영향을 받고, 그 인쪽 좌석이 영향을 받고… 이런 식)
– 회전하는 자석 기준으로 회전 가능한 방향을 계속 swap (1->-1->1->…)하면서 업데이트
– 연쇄적으로 처리할 때, 직전 자석 (왼쪽으로 갈 때는 자기 오른쪽, 오른쪽으로 갈 때는 자기 왼쪽)과 현재 자석이 맞닿은 두 극이 다를 때만 회전 가능으로 처리 (이외의 경우 회전하지 않음)
직전 좌석이 회전하지 않으면 무조건 현재 자석은 회전하지 않도록 함
– 지정한 만큼 자석이 회전되고 나면, 점수를 구함.

import java.io.*;

public class Solution {
	public static final int numMagnetic = 4;
	public static final int numTooth = 8;
	
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int num = 0; num < numCases; num++) {
				writer.write("#" + String.valueOf(num + 1) + " ");
				
				int numK = Integer.parseInt(reader.readLine()); // 회전 케이스 갯수 
				int[][] magneticInfo = new int[numMagnetic][numTooth]; // idx1: 0~3 (n번째 자석) / idx2: 0~7 (n번째 날) / N극: 0, S극: 1
				int[] arrowIdx = new int[numMagnetic]; // 화살표 idx / idx1: 0~3 (n번째 자석) / 0~7 (n번째 날)
				int[] leftIdx = new int[numMagnetic]; // 맨 왼쪽 부분 idx / idx1: 0~3 (n번째 자석) / 0~7 (n번째 날)
				int[] rightIdx = new int[numMagnetic]; // 맨 오른쪽 부분 idx / idx1: 0~3 (n번째 자석) / 0~7 (n번째 날)
								
				// 자석 map 만들기
				for (int i = 0; i < numMagnetic; i++) {
					String[] tmp = reader.readLine().split(" ");
					
					for (int j = 0; j < tmp.length; j++) 
						magneticInfo[i][j] = Integer.parseInt(tmp[j]);
					
					leftIdx[i] = 6; // -2, +8 하면 6과 동일 
					rightIdx[i] = 2;// +2
				}
				
				boolean[] willRotate = new boolean[numMagnetic]; // 실제 회전 여부 (true: 회전, false: 비회전)
				int[] rotateDirection = new int[numMagnetic]; // -1: 반시계 (왼쪽), 1: 시계 (오른쪽)
				
				// 실제 회전 처리 
				for (int i = 0; i < numK; i++) {
					String[] tmp_ = reader.readLine().split(" ");
					int triggerIdx = Integer.parseInt(tmp_[0]) - 1; // 1~4번째로 되어있으므로 0~3으로 수정
					
					for (int j = 0; j < numMagnetic; j++) {
						willRotate[j] = false;
					}
					
					// 직접 돌리는 자석은 무조건 회전됨
					willRotate[triggerIdx] = true;
					rotateDirection[triggerIdx] = Integer.parseInt(tmp_[1]);
					
					// 현재 자석 기준 오른쪽 처리
					for (int j = triggerIdx + 1; j < numMagnetic; j++) {
						// 왼쪽 자석이 회전하고, 왼쪽 자석 오른극과 지금 자석 왼극이 다른 경우 회전 정보 갱신
						if (willRotate[j - 1] == true && magneticInfo[j - 1][rightIdx[j - 1]] != magneticInfo[j][leftIdx[j]]) {
							willRotate[j] = true;
						}
						rotateDirection[j] = -rotateDirection[j - 1]; // 반대로 회전
					}
					
					// 현재 자석 기준 왼쪽 처리
					for (int j = triggerIdx - 1; j >= 0; j--) {
						// 오른쪽 자석이 회전하고, 오른쪽 자석 왼극과 지금 자석 오른극이 다른 경우 회전 정보 갱신
						if (willRotate[j + 1] == true && magneticInfo[j + 1][leftIdx[j + 1]] != magneticInfo[j][rightIdx[j]]) {
							willRotate[j] = true;
						}
						rotateDirection[j] = -rotateDirection[j + 1]; // 반대로 회전
					}

					// 회전 후 정보 처리
					for (int j = 0; j < numMagnetic; j++) {
						if (willRotate[j] == true) {
							switch (rotateDirection[j]) {
							case -1: // 반시계
								arrowIdx[j]++;
								leftIdx[j]++;
								rightIdx[j]++;
								
								arrowIdx[j] %= numTooth;
								leftIdx[j] %= numTooth;
								rightIdx[j] %= numTooth;

								break;
							case 1: // 시계
								arrowIdx[j]--;
								leftIdx[j]--;
								rightIdx[j]--;
								
								if (arrowIdx[j] < 0)
									arrowIdx[j] += numTooth;
								if (leftIdx[j] < 0)
									leftIdx[j] += numTooth;
								if (rightIdx[j] < 0)
									rightIdx[j] += numTooth;
								
								break;
							}
						}
					}
					
				}

				int answer = 0;
				for (int i = 0; i < numMagnetic; i++) {
					// 각 화살표 부분의 값이 S극일 경우 점수 더함  
					if (magneticInfo[i][arrowIdx[i]] == 1)
						answer += 1 << i;
				}
				writer.write(answer + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

(JAVA) 2383. [모의 SW 역량테스트] 점심 식사시간

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl

단계별로 잘 나눠야 하는 문제였음.
– 계단입구는 2개로 보장되어 있고, 사람 수만 변동성이 있음. 최대 10명이 조건이라서 아예 사람 관련 배열은 크기를 10으로 사용
– 각 사람이 계단입구1로 가느냐 2로 가느냐이니까, 경우의 수는 2^사람수 임.
– 각 사람의 정보를 1분 단위로 업데이트하는 식으로 구현.
– 처음에는 상태 0 (계단 입구로 가는 중)에 계단 입구로 가는 시간이 입력되어 있음. 상태 0일 때는 1분씩 감소시키고, 0분이 되면 상태1 (계단 입구 도착)으로 업데이트.
– 상태 1 (계단 입구 도착)일 때는 해당하는 계단에 3명 미만으로 있을 경우만 진입 (상태 2로 업데이트하고, 계단에 있어야 하는 시간 입력) / 이외의 경우에는 계속 상태 1에 있음
– 상태 2 (계단으로 이동 중)의 경우에는 시간 정보를 1 감소하고, 0이 되면 상태 3 (완료)로 이동.
단, 사람의 정보를 순차적으로 업데이트하기 때문에, 계단에서 사람이 나오는 정보가 늦게 업데이트되서 실제로는 계단 진입이 가능한데 불가능한 경우로 처리될 수 있음. 이 경우를 대비해서, 두 번째 상태 체크 (상태1->상태2로 이동) 로직을 추가로 구현함.

import java.io.*;
import java.util.*;

public class Solution {
	public static final int manMax = 10;
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int num = 0; num < numCases; num++) {
				writer.write("#" + String.valueOf(num + 1) + " ");
				
				int numN = Integer.parseInt(reader.readLine()); // 지도 크기 
				
				// 계단입구 정보 (X, Y, 시간)
				int stairCount = 0;
				int[] stairX = new int[2];
				int[] stairY = new int[2];
				int[] stairCost = new int[2];
				
				// 사람 정보 (X, Y, 목적지)
				int manCount = 0;
				int[] manX = new int[manMax];
				int[] manY = new int[manMax];
				int[] manDest = new int[manMax];				
				int[] manStatus = new int[manMax]; // 0: 계단 입구로 가는 중, 1: 입구 도착, 2: 계단으로 이동 중, 3: 완료 
				int[] manMin = new int[manMax];
				
				// 사람, 계단 정보 생성
				for (int i = 0; i < numN; i++) {
					String[] tmp = reader.readLine().split(" ");

					for (int j = 0; j < tmp.length; j++) {
						int nextInfo = Integer.parseInt(tmp[j]);
						
						if (nextInfo == 0)
							continue;
						else {
							if (nextInfo == 1) { // 사람
								manX[manCount] = j;
								manY[manCount] = i;
								manCount++;
							}
							else {				 // 계단입구
								stairX[stairCount] = j;
								stairY[stairCount] = i;
								stairCost[stairCount] = nextInfo;
								stairCount++;
							}
						}						
					}
				}

				// 각 사람이 계단입구 1이나 2로 가니까 2^사람수 - 1 개 만큼 경우의 수가 생김
				int allPossibility = (int) Math.pow(2, manCount) - 1;

				// 최소값을 저장해야 하므로 최초 값은 매우 큰 수로 넣음
				int answer = 10000;
				
				// 실제 소요 시간 계산
				for (int i = 0; i <= allPossibility; i++) {
					int tmp_ =  i;

					List<String> stairZero = new ArrayList<String>(); // 첫번째 계단을 향하는 사람들 
					List<String> stairOne = new ArrayList<String>();  // 두 번째 계단을 향하는 사람들 
										
					// 목적지 입력
					for (int j = 0; j < manCount; j++) {
						manStatus[j] = 0;
						manDest[j] = tmp_ & 0b1;
												
						// 계단입구까지 걸리는 시간 계산
						manMin[j] = Math.abs(stairX[manDest[j]] - manX[j]) + Math.abs(stairY[manDest[j]] - manY[j]);
						
						tmp_ = tmp_ >> 1;
					}

					// 시간 소요 체크
					int minute = 0;
					while(true) {
						// 모든 사람이 이미 도착한 경우 루프를 나가도록 함 
						boolean allDone = true;
						for (int j = 0; j < manCount; j++) {
							if (manStatus[j] != 3) {
								allDone = false;
								break;
							}
						}
						if (allDone == true)
							break;
						
						for (int j = 0; j < manCount; j++) {
							switch (manStatus[j]) {
							case 0: // 계단 입구로 가는 중 
								if (manMin[j] == 0) {
									manStatus[j] = 1; // 입구 도착으로 변경
								}
								else
									manMin[j]--; // 0 될 때까지 감소
								break;
							case 1: // 입구 도착
								// 계단에 3명 이하만 있게 함 (초과하면 계속 status 1에 머무름)
								switch (manDest[j]) {
								case 0:
									if (stairZero.size() < 3) {
										stairZero.add(String.valueOf(j));
										manStatus[j] = 2; // 계단으로 이동중
										manMin[j] = stairCost[0];
									}
									break;
								case 1:
									if (stairOne.size() < 3) {
										stairOne.add(String.valueOf(j));
										manStatus[j] = 2; // 계단으로 이동중
										manMin[j] = stairCost[1];
									}
									break;
								}
								break;
							case 2: // 계단으로 이동 중
								manMin[j]--;
								
								if (manMin[j] == 0) {
									switch (manDest[j]) {
									case 0:
										stairZero.remove(String.valueOf(j));
										break;
									case 1:
										stairOne.remove(String.valueOf(j));
										break;
									}
									
									manStatus[j] = 3; // 완료
								}
									
								break;
							case 3: // 완료 
								continue;
							}
						}
						
						// 입구에 있는 경우만 다시 한 번 계산 (이미 나간 사람이 있을 경우 다시 진입 가능하도록 함)
						for (int j = 0; j < manCount; j++) {
							switch (manStatus[j]) {
							case 1: // 입구 도착
								// 계단에 3명 이하만 있게 함 (초과하면 계속 status 1에 머무름)
								switch (manDest[j]) {
								case 0:
									if (stairZero.size() < 3) {
										stairZero.add(String.valueOf(j));
										manStatus[j] = 2; // 계단으로 이동중
										manMin[j] = stairCost[0];
									}
									break;
								case 1:
									if (stairOne.size() < 3) {
										stairOne.add(String.valueOf(j));
										manStatus[j] = 2; // 계단으로 이동중
										manMin[j] = stairCost[1];
									}
									break;
								}
								break;
							}
						}	
						
						minute++;						
					}
					
					if (minute < answer)
						answer = minute;
				}
				
				writer.write(answer + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

(JAVA) 2382. [모의 SW 역량테스트] 미생물 격리

Standard

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

크게 복잡하지는 않았던 문제.
– 맵 만들고 나서, 매 시간 1. 정해진 대로 이동 후 방향과 갯수 수정이 필요한 경우 수정 2. 같은 위치에 있는 군집들을 merge 하도록 구현
– 정해진 시간이 끝난 후, 각 군집의 갯수를 더하면 정답

import java.io.*;
import java.util.*;

public class Solution {
	
	public static void main(String[] args) throws IOException {
		// System.setIn(new FileInputStream("./src/sample_input.txt"));
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int num = 0; num < numCases; num++) {
				writer.write("#" + String.valueOf(num + 1) + " ");
				
				String[] tmp = reader.readLine().split(" ");
				int numN = Integer.parseInt(tmp[0]); // 셀 갯수
				int numM = Integer.parseInt(tmp[1]); // 격리 시간
				int numK = Integer.parseInt(tmp[2]); // 미생물 갯수
				
				int[] arrayY = new int[numK];	// 세로 위치
				int[] arrayX = new int[numK];	// 가로 위치
				int[] arrayNum = new int[numK];	// 미생물 수
				int[] arrayMove = new int[numK];// 이동 방향 (1: 상, 2: 하, 3: 좌, 4: 우)
				
				// Map 생성
				for (int i = 0; i < numK; i++) {
					String[] tmp_ = reader.readLine().split(" ");
					
					arrayY[i] = Integer.parseInt(tmp_[0]);
					arrayX[i] = Integer.parseInt(tmp_[1]);
					arrayNum[i] = Integer.parseInt(tmp_[2]);
					arrayMove[i] = Integer.parseInt(tmp_[3]);
				}
				
				// 시간 단위 처리 
				for (int i = 0; i < numM; i++) {
					// 각 미생물 별로 처리 
					for (int j = 0; j < numK; j++) {
						if (arrayNum[j] == 0) // 전부 죽은 경우 혹은 합쳐져서 무효화된 경우 확인할 필요가 없음
							continue;
						
						switch (arrayMove[j]) { // 이동
						case 1: // 상 
							arrayY[j]--;
							break;
						case 2: // 하
							arrayY[j]++;
							break;
						case 3: // 좌 
							arrayX[j]--;
							break;
						case 4: // 우
							arrayX[j]++;
							break;
						}
						
						if (arrayY[j] == 0) { // 맨 위에 닿은 경우
							arrayNum[j] /= 2;
							arrayMove[j] = 2; // 상에서 하로 변경 
						}						
						else if (arrayY[j] == numN - 1) { // 맨 아래에 닿은 경우
							arrayNum[j] /= 2;
							arrayMove[j] = 1; // 하에서 상으로 변경 
						}
						else if (arrayX[j] == 0) { // 맨 왼쪽에 닿은 경우
							arrayNum[j] /= 2;
							arrayMove[j] = 4; // 좌에서 우로 변경 
						}						
						else if (arrayX[j] == numN - 1) { // 맨 오른쪽에 닿은 경우
							arrayNum[j] /= 2;
							arrayMove[j] = 3; // 우에서 좌로 변경 
						}
					}
					
					// 합칠 필요가 있는 경우 합침 
					for (int j = 0; j < numK; j++) {
						if (arrayNum[j] == 0) // 전부 죽은 경우 확인할 필요가 없음
							continue;
						
						int Y = arrayY[j];
						int X = arrayX[j];
						int max = j;
						int total = arrayNum[j];
						
						// 같은 위치에 있는 다른 군집들 탐색
						List<Integer> sameLocation = new ArrayList<Integer>();
						
						// 자기 이전의 군집들은 탐색할 필요가 없음 (아직 같은 위치를 찾아본 적이 없는 경우만 여기 도달)
						for (int k = j + 1; k < numK; k++) {
							if (arrayNum[k] != 0 && arrayY[k] == Y && arrayX[k] == X) {
								sameLocation.add(k);
								total += arrayNum[k];
								if (arrayNum[max] < arrayNum[k])
									max = k;
							}
						}
						
						if (sameLocation.size() != 0) {
							// 갯수가 제일 많은 군집의 방향 이용
							arrayMove[j] = arrayMove[max];
							// 총 갯수 넣음
							arrayNum[j] = total;
							
							// j 외의 군집 내용은 모두 무효화
							for (int idx: sameLocation) {
								arrayY[idx] = -1; // 무효화 
								arrayX[idx] = -1; // 무효화
								arrayNum[idx] = 0;
							}
						}
					}
				}
				
				// 정답 구하기
				int answer = 0;
				for (int i = 0; i < numK; i++)
					answer += arrayNum[i];
				
				writer.write(answer + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

(JAVA) 2117. [모의 SW 역량테스트] 홈 방범 서비스

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

오랜만에 다시 풀다 보니 머리가 안 돌아가서 고생함.
– 홈 방범 영역을 계산하기 위해 k=1일 때 가운데를 0,0으로 해서 1군데 넣고, k=2일 때 -1,0 / 1,0 / 0,-1 / 0,1 4군데 넣고 (규칙이라면 마름모 꼴로 해서 x+y가 k-1인 모든 정수로 된 점을 넣는 식으로..) 이런 식으로 홈방범 영역 계산
– 처음에는 k=1부터 해서 늘려나가는 식으로 짰는데, 시간 초과가 나와서 로직 수정
– 처음에 map 만들 때 집 갯수를 세서, 집 갯수*비용이 운영 비용 (k-1 제곱+k 제곱)보다 작아지는 최초의 k를 구해서 k-1을 maxBound로 이용 (즉 이보다 큰 maxBound는 고려할 필요가 없음)
– k=maxBound부터 1씩 줄여나가면서 손해가 안나는 (>=0) 최초의 k가 나올 때까지 ‘서비스가 제공되는 집의 갯수’를 구함. 그랬더니 3초 기준으로 1.6초인가 해서 통과.

import java.io.*;
import java.util.*;

public class Solution {
	
	public static void main(String[] args) throws IOException {
		// System.setIn(new FileInputStream("./src/sample_input.txt"));
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int i = 0; i < numCases; i++) {
				writer.write("#" + String.valueOf(i + 1) + " ");
				
				String[] tmp = reader.readLine().split(" ");
				int numN = Integer.parseInt(tmp[0]); // 도시 크기
				int numM = Integer.parseInt(tmp[1]); // 지불 비용
				
				// N, M 출력
				//writer.write(numN + " " + numM + System.lineSeparator());
				
				int[][] map = new int[numN][numN];
				int numAllHouse = 0;

				// 맵 생산
				for (int j = 0; j < numN; j++) {
					String[] tmp_ = reader.readLine().split(" ");
					
					for (int k = 0; k < tmp_.length; k++) {
						if (tmp_[k].equals("1")) {
							map[k][j] = 1;
							numAllHouse++;
						}
					}
				}
				
				List<String> serviceArea = new ArrayList<String>();
				
				int maxHouse = 0;
				
				// 서비스 영역 최대값 구하기
				int maxBound = 1;
				while(maxBound * maxBound + (maxBound - 1) * (maxBound - 1) < numAllHouse * numM) {
					maxBound++;
				}
				maxBound--; // while 문에서 탈출할 때는 이미 서비스 비용이 제공 수수료를 초과하므로, maxBound를 1 줄임 (서비스 비용이 제공 수수료보다 작은 최대값)
				
				while (true) {
					serviceArea.clear();
					
					// 서비스 영역 처리
					for (int j = 0; j < maxBound; j++) {
						if (j == 0)
							serviceArea.add("0/0");
						else {
							for (int k = 0; k <= j; k++) {
								int l = j - k;
								
								int tmp1 = k;
								int tmp2 = l;
								
								if (serviceArea.contains(tmp1 + "/" + tmp2) == false)
									serviceArea.add(tmp1 + "/" + tmp2);
								
								tmp1 = -k;
								tmp2 = l;
								
								if (serviceArea.contains(tmp1 + "/" + tmp2) == false)
									serviceArea.add(tmp1 + "/" + tmp2);
								
								tmp1 = k;
								tmp2 = -l;
								
								if (serviceArea.contains(tmp1 + "/" + tmp2) == false)
									serviceArea.add(tmp1 + "/" + tmp2);
								
								tmp1 = -k;
								tmp2 = -l;
								
								if (serviceArea.contains(tmp1 + "/" + tmp2) == false)
									serviceArea.add(tmp1 + "/" + tmp2);
							}
						}
					}
					
					// 실제 손익 계산 (하나씩 늘려가면서 해야되므로 loop 안에서 수행)
					int operationalCost = serviceArea.size();
					
					// k: 기준점 x, l: 기준점 y
					for (int k = 0; k <= numN - 1; k++) {
						for (int l = 0; l <= numN - 1; l++) { int count = 0; for (String entry: serviceArea) { String[] tmp__ = entry.split("/"); int x = k + Integer.parseInt(tmp__[0]); int y = l + Integer.parseInt(tmp__[1]); if (x >= 0 && x < numN && y >= 0 && y < numN) { if (map[x][y] == 1) count++; } } if (numM * count - operationalCost >= 0) { 
								if (maxHouse < count)
									maxHouse = count;								
							}
						}
					}
					
					if (maxHouse == 0) 
						maxBound--;
					else 
						break;
				}
				
				writer.write(maxHouse + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

(Java) 2112. [모의 SW 역량테스트] 보호 필름

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu

왜 정답률이 낮은지 깨달은 문제.
– 뭔가 다른 방식의 완전 탐색으로 푸니까 시간 초과가 떠서 머리를 다시 굴림.
– 결국 각 막마다 A를 칠할 것이냐, B를 칠할 것이냐, 칠하지 않을 것이냐 해서 DFS로 모든 경우의 수를 탐색하는 문제였음.
– 각 막의 약품 처리 여부에 따라 지도가 계속 정보가 바뀌는데, 지도 전체를 계속 복사해서 쓰면 시간 소요가 크기 때문에, 수정하는 부분 (한 줄)만 백업해두고 값 바꾼 후 다시 값 복원하는 식으로 시간 효율을 올림.
– 어째저째 겨우겨우 통과함. 완전 탐색으로 짤 때, 쉽게 생각해야 가짓수를 쓸데없이 늘리는 실수를 안 함.

import java.io.*;
import java.util.*;

public class Solution {
	public static int minLevel = 1000;	// 최소값 찾는 것이기 때문에 최대 가능한 값보다 큰 값으로
	
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));

		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int i = 0; i < numCases; i++) {
				writer.write("#" + String.valueOf(i + 1) + " ");

				// 최소값 찾는 것이기 때문에 최대한 큰 값으로
				minLevel = 1000;

				// height: 두께 (Y), width: 가로크기 (X), threshold: 합격기준 
				String[] tmp = reader.readLine().split(" ");

				int height = Integer.parseInt(tmp[0]);
				int width = Integer.parseInt(tmp[1]);
				int threshold = Integer.parseInt(tmp[2]);

				// map 제작
				int[][] map = new int[height][width];
				for (int j = 0; j < height; j++) {
					String[] tmp_ = reader.readLine().split(" ");
					for (int k = 0; k < tmp_.length; k++) {
						map[j][k] = Integer.parseInt(tmp_[k]);
					}
				}
		
				// 한 번에 통과하는지 체크 
				if (checkPass(map, threshold) == true) {
					writer.write("0" + System.lineSeparator());
					continue;
				}
				// 안 되는 경우, 쭉 체크
				process(0, map, 0, threshold);

				writer.write(minLevel + System.lineSeparator());
				writer.flush();
			}			
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}	
	
	public static void process(int depth, int[][] map, int numTry, int threshold) {
		// 마지막 depth까지 안 되서 온 경우, 각 경우 처리 
		if (depth == map.length - 1) {
			// 안 고치고 가능한지 시도 (가장 적은 numTry 경우)
			if (checkPass(map, threshold) == true) {
				if (minLevel > numTry)
					minLevel = numTry;
				return;
			}
			
			// A 칠하고 나서 통과 여부 검사 
			// 지도 복구하기 위한 정보들 
			int[] toRestore = new int[map[depth].length];
			for(int i = 0; i < map[depth].length; i++)
				toRestore[i] = map[depth][i];
			Arrays.fill(map[depth], 0); // 0: A

			// A 칠해서 통과하면, 더 진행할 필요가 없음
			if (checkPass(map, threshold) == true) {
				if (minLevel > numTry + 1)
					minLevel = numTry + 1;
				
				// 갔다온 후 지도 복구
				for(int i = 0; i < map[depth].length; i++)
					map[depth][i] = toRestore[i];	

				return;
			}
			else {
				// 갔다온 후 지도 복구
				for(int i = 0; i < map[depth].length; i++)
					map[depth][i] = toRestore[i];	
			}
			
			// B 칠하고 나서 통과 여부 검사
			// 지도 복구하기 위한 정보들 
			toRestore = new int[map[depth].length];
			for(int i = 0; i < map[depth].length; i++)
				toRestore[i] = map[depth][i];
			Arrays.fill(map[depth], 1); // 1: B

			// B 칠해서 통과하면, 더 진행할 필요가 없음
			if (checkPass(map, threshold) == true) {
				if (minLevel > numTry + 1)
					minLevel = numTry + 1;
				
				// 갔다온 후 지도 복구
				for(int i = 0; i < map[depth].length; i++)
					map[depth][i] = toRestore[i];	
			}
			else {
				// 갔다온 후 지도 복구
				for(int i = 0; i < map[depth].length; i++)
					map[depth][i] = toRestore[i];	
			}
			
			return;	
		}
		
		// Case 1: A (A 칠하고 통과 여부 검사)
		int[] toRestore = new int[map[depth].length];
		for(int i = 0; i < map[depth].length; i++)
			toRestore[i] = map[depth][i];
		Arrays.fill(map[depth], 0);

		// A 칠해서 통과하면, 더 진행할 필요가 없음
		if (checkPass(map, threshold) == true) {
			if (minLevel > numTry + 1)
				minLevel = numTry + 1;
			
			// 갔다온 후 지도 복구
			for(int i = 0; i < map[depth].length; i++)
				map[depth][i] = toRestore[i];	

			return;
		}
		else {
			// A를 칠한 경우이므로 numTry 1 증가
			process(depth + 1, map, numTry + 1, threshold);			
		
			// 갔다온 후 지도 복구
			for(int i = 0; i < map[depth].length; i++)
				map[depth][i] = toRestore[i];
		}
		
		// Case 2: B (B 칠하고 통과 여부 검사)
		toRestore = new int[map[depth].length];
		for(int i = 0; i < map[depth].length; i++)
			toRestore[i] = map[depth][i];
		Arrays.fill(map[depth], 1);
		
		//B 칠해서 통과하면, 더 진행할 필요가 없음
		if (checkPass(map, threshold) == true) {
			if (minLevel > numTry + 1)
				minLevel = numTry + 1;

			// 갔다온 후 지도 복구
			for(int i = 0; i < map[depth].length; i++)
				map[depth][i] = toRestore[i];	
			
			return;
		}
		else {
			// B를 칠한 경우이므로 numTry 1 증가
			process(depth + 1, map, numTry + 1, threshold);	

			// 갔다온 후 지도 복구
			for(int i = 0; i < map[depth].length; i++)
				map[depth][i] = toRestore[i];	
		}

		// Case 3: X (약품 처리 안하고 통과 여부 검사)
		if (checkPass(map, threshold) == true) {
			if (minLevel > numTry)
				minLevel = numTry;
			return;
		}
		else {
			// 약품 처리 안 했으므로, numTry는 그대로
			process(depth + 1, map, numTry, threshold);
		}
	}
	
	public static boolean checkPass(int[][] map, int threshold) {
		boolean passed = true;
		
		// 시험 통과 여부 판별
		for (int i = 0; i < map[0].length; i++) {
			int currentIdx = map[0][i];
			int count = 1;

			for (int j = 1; j < map.length; j++) {
				if (currentIdx == map[j][i]) {
					count++;
					
					// 이미 합격한 경우 더 이상 진행하지 않음
					if (count == threshold)
						break;
				}
				else { // 달라진 경우 
					currentIdx = map[j][i];
					count = 1;
				}
			}
			
			// threshold를 넘긴 경우가 없을 경우, 실패로 처리하고 return
			if (count < threshold) {
				passed = false;
				break;
			}
		}
		
		return passed;
	}
}