[codeTree, 자바] 술래 잡기

0. 문제 링크

https://www.codetree.ai/frequent-problems/hide-and-seek/description

코드트리

---

1. 문제 핵심

1. 나무와 겹치는 도망자는 잡히지 않는다.
2. 술래는 격자의 크기와 상관없이 자신의 자리를 포함한 3칸 내의 도망자만 잡는다.
3. 도망자는 이동 중 술래와 겹칠 수 없다.

---

2. 문제 접근

1. 도망자 이동, 술래 이동(및 회전), 술래 잡기, 총 세 단계로 진행되게끔 모듈화했습니다.
2. 모듈화하였음에도 디버깅이 오래 걸렸는데 일단 구현할 것들도 꽤 많지만 가장 큰 실수로 3칸 내에서 이동 가능한 도망자 탐색과 도망자 이동을 동시에 진행해서 이미 이동을 마친 도망자를 또 이동시킨 것이었습니다.
3. 만약 틀린 테스트 케이스를 확인하지 못하고 IDE를 쓸 수 없었다면 문제 해결하는 것이 쉽지 않았을 것 같습니다.

---

3. 내 코드 분석

술래의 좌표, 현재 바라보는 방향, 진행 구간과 위치, 회전 방향을 저장

진행 구간을 정의 및 초기화

n이 5인 경우 turnCount = { 1, 1, 2, 2, 3, 3, 4, 4, 4 };

n이 7인 경우 turnCount = { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 6 };

나선의 구간이 규칙성있게 생성됨

2차원 List 배열에 도망자들을 유동적으로 저장

도망자 이동, 술래 이동, 술래 검거 순으로 진행

 

 

---

4. 베스트 코드 분석

---

5. 코드

package algo;

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

public class 술래잡기 {
	static int[][] bd;
	static int[][] runner;
	static int[][] dydx = new int[][] { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
	static int[] turnCount;
	static int[] catcher;
	static Queue<int[]> q = new LinkedList<>();
	static int n;
	static List<Integer>[][] mapList;
	static int[][] debug;

	public static void Running() {
//		Queue<int[]> tmpQ = new LinkedList<>();
		Queue<int[]> afterRun = new LinkedList<>();
		q.add(catcher);
		int[] crnt;
		int nextY, nextX;
		boolean[][] isVisit = new boolean[n][n];
		while (!q.isEmpty()) {
			crnt = q.poll();

			for (int i = 0; i < 4; i++) {
				nextY = crnt[0] + dydx[i][0];
				nextX = crnt[1] + dydx[i][1];

				if (nextY < 0 || nextX < 0 || nextY == n || nextX == n)
					continue;
				// 거리가 3칸 초과인 경우 패스
				if (Math.abs(catcher[0] - nextY) + Math.abs(catcher[1] - nextX) > 3)
					continue;

				if (isVisit[nextY][nextX])
					continue;

				isVisit[nextY][nextX] = true;
				// 범위 탐색을 위해 추가
				q.add(new int[] { nextY, nextX });

				// 도망자가 저장되어있는 경우
				if (mapList[nextY][nextX].size() != 0) {
					// 해당 자리 도망자들을 목록화
					Object[] runners = mapList[nextY][nextX].toArray();
					// 그 자리 초기화
					mapList[nextY][nextX].clear();
					// 각 도망자 번호를 순회하며 위치를 변경
					for (Object l : runners) {
						// 도망자의 다음번 자리 계산
						int runnerNextY = runner[(int) l][0] + dydx[runner[(int) l][2]][0];
						int runnerNextX = runner[(int) l][1] + dydx[runner[(int) l][2]][1];

						// 다음 자리가 외곽인 경우
						if (runnerNextY < 0 || runnerNextY == n || runnerNextX < 0 || runnerNextX == n) {
							// 방향 전환 완료
							runner[(int) l][2] = (runner[(int) l][2] + 2) % 4;

							// 방향 전환했기 때문에 다음 자리 다시 계산
							runnerNextY = runner[(int) l][0] + dydx[runner[(int) l][2]][0];
							runnerNextX = runner[(int) l][1] + dydx[runner[(int) l][2]][1];

						}

						// 한칸 전진하는 자리에 술래가 있는 경우
						if (catcher[0] == runnerNextY && catcher[1] == runnerNextX) {
							// 움직일 수 없기 때문에 같은 자리에 다시 재입력
//							mapList[nextY][nextX].add((int) l);
							afterRun.add(new int[] { nextY, nextX, (int) l });
							continue;
						}
						// 술래가 없는 경우
						// 다음 자리에 도망자 추가
//						mapList[runnerNextY][runnerNextX].add((int) l);
						afterRun.add(new int[] { runnerNextY, runnerNextX, (int) l });
						// 도망자 최신 위치 변경
						runner[(int) l][0] = runnerNextY;
						runner[(int) l][1] = runnerNextX;
					}

					// 한번에 모두 저장하고 나중에 처리해야 함
//					tmpQ.add(new int[] { nextY, nextX });

				}
			}
		}

		// 모아두었던 이동한 도망자들 원본 배열에 반영
		while (!afterRun.isEmpty()) {
			crnt = afterRun.poll();
			mapList[crnt[0]][crnt[1]].add(crnt[2]);
		}
	}

	public static void Moving() {
		// 새로운 위치
		debug[catcher[0]][catcher[1]]--;
		catcher[0] = catcher[0] + dydx[catcher[2]][0];
		catcher[1] = catcher[1] + dydx[catcher[2]][1];
		debug[catcher[0]][catcher[1]]++;
		// 스택 추가
		catcher[4]++;

		// 회전 위치에 도달
		if (turnCount[catcher[3]] == catcher[4]) {
			// 정방향인 경우
			if (catcher[5] == 0) {
				catcher[2] = (catcher[2] + 1) % 4;
				// 다음 진행 상황으로 진행
				catcher[3]++;
			}
			// 역방향인 경우
			else {
				catcher[2] = catcher[2] - 1;
				if (catcher[2] < 0)
					catcher[2] = 3;
				catcher[3]--;
			}

			// 마지막 포인트에 도달했다면
			if (catcher[3] == n * 2 - 1) {
				// 역방향으로 전환
				catcher[5] = 1;
				// 마지막 진행 다시 시작
				catcher[3] = n * 2 - 2;
				// 방향 아래로 변환
				catcher[2] = 2;
			}
			// 첫 포인트에 도달했다면
			else if (catcher[3] == -1) {
				// 정방향으로 전환
				catcher[5] = 0;
				// 0번째 진행 상황으로 초기화
				catcher[3] = 0;
				// 방향 위로 전환
				catcher[2] = 0;
			}
			// 스택 초기화
			catcher[4] = 0;
		}
	}

	public static int Catching() {
		int nextY = catcher[0], nextX = catcher[1], cnt = 0, limit = 0;

		// 범위 벗어나지 않는 선에서 자신 칸 포함해 3칸만 검사
		while (nextY >= 0 && nextY < n && nextX >= 0 && nextX < n && limit < 3) {
			// 나무가 존재하지 않는 곳만
			if (bd[nextY][nextX] == 0) {
				cnt += mapList[nextY][nextX].size();
				mapList[nextY][nextX].clear();
			}

			nextY += dydx[catcher[2]][0];
			nextX += dydx[catcher[2]][1];
			limit++;
		}
		return cnt;
	}

	public static void main(String[] args) throws IOException {
		// n 크기 m 도망자 수 h 나무 수 k: 턴 수
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int answer = 0, cntRunner = 0;
		n = Integer.parseInt(st.nextToken());

		// 0: Y, 1: X, 2: 전진 방향, 3: 진행 구간, 4: 진행 구간 스택(진행된 정도), 5: 0->시계, 1->반시계
		catcher = new int[6];
		// 술래 Y
		catcher[0] = n / 2;
		// 술래 X
		catcher[1] = n / 2;

		// n*n 크기의 List 선언
		mapList = new List[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				mapList[i][j] = new LinkedList<>();
			}
		}

		// 술래의 방향 전환 검사
		turnCount = new int[n * 2 - 1];
		int cnt = 1;
		for (int i = 0; i < n * 2 - 2; i++) {
			turnCount[i] = cnt;

			if (i % 2 == 1)
				cnt++;
		}
		turnCount[n * 2 - 2] = cnt - 1;

		int m = Integer.parseInt(st.nextToken());
		// 0: y, 1: x, 2: 현재 방향
		runner = new int[m][3];
		// 나무 수
		int h = Integer.parseInt(st.nextToken());
		// 턴 수
		int k = Integer.parseInt(st.nextToken());

		// 0: 나무 존재 여부,
		bd = new int[n][n];

		// 도망자 입력
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			runner[i][0] = Integer.parseInt(st.nextToken()) - 1;
			runner[i][1] = Integer.parseInt(st.nextToken()) - 1;
			// 1: 좌우, 2: 상하
			runner[i][2] = Integer.parseInt(st.nextToken());
			// y, x에 해당 사람 저장
			mapList[runner[i][0]][runner[i][1]].add(i);
		}

		// 나무 위치 저장
		for (int i = 0; i < h; i++) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken()) - 1;
			int x = Integer.parseInt(st.nextToken()) - 1;
			bd[y][x] = 1;
		}
		debug = new int[n][n];
		debug[n / 2][n / 2]++;
		// k 턴 진행
		for (int i = 1; i <= k; i++) {
			// 도망자 이동
			Running();
			// 술래 이동
			Moving();
			// 술래 검거
			cntRunner = Catching();
			answer += cntRunner * i;
		}
		System.out.println(answer);
	}
}