[알고리즘][X] 술래 잡기

https://www.codetree.ai/training-field/frequent-problems/problems/hide-and-seek/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static class Node{
		Point point;
		Point dir;
		public Node(Point point, Point dir) {
			super();
			this.point = point;
			this.dir = dir;
		}
		@Override
		public String toString() {
			return "Node [point=" + point + ", dir=" + dir + "]";
		}
		
		
	}
	static int n;
	static int m;
	static int h;
	static int k;

	static int[][] runner;
	static boolean[][] tree;
	static int[] dx = {1, 0, 0, -1};
	static int[] dy = {0, 1, -1, 0};
	static List<Node> res;
	static int score;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		h = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		score = 0;
		runner = new int[m][4];
		tree = new boolean[n][n];
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 2; j++) {				
				runner[i][j] = Integer.parseInt(st.nextToken()) - 1;
			}
			int dir = Integer.parseInt(st.nextToken());
			if (dir == 1) {
				runner[i][2] = 1;
			} else {
				runner[i][2] = 0;
			}
		}

		for (int i = 0; i < h; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			tree[x][y] = true;
		}
		
		res = new ArrayList<>();
		res.add(new Node(new Point(n/2, n/2), new Point(-1, 0)));
		res.addAll(forward(n));
		res.addAll(backward(n));
//		System.out.println(res);
		
		for (int i = 0; i < k; i++) {
			playGame(i);
		}
		
		System.out.println(score);
	}

	private static void playGame(int t) {
		for (int i = 0; i < m; i++) {
			if (runner[i][3] == 1) {
				continue;
			}
			
			int x = runner[i][0];
			int y = runner[i][1];
			int dir = runner[i][2];
			Node node = res.get(t % res.size());
			Point cur = node.point;
			int dist = Math.abs(cur.x - x) + Math.abs(cur.y - y);
			if (dist <= 3) {
				int nx = x + dx[dir];
				int ny = y + dy[dir];
				
				if (!(0 <= nx && nx < n && 0 <= ny && ny < n)) {
					dir = 3 - dir;
					nx = x + dx[dir];
					ny = y + dy[dir];
					runner[i][2] = dir;
				}
				
				if (!(cur.x == nx && cur.y == ny)) {
					runner[i][0] = nx;
					runner[i][1] = ny;
				}
			}
		}
		
		
		Node node = res.get((t+1) % res.size());
		Point cur = node.point;
		Point dir = node.dir;
		
		int nx = cur.x;
		int ny = cur.y;
		for (int k = 0; k < 3; k++) {

		if (!(0 <= nx && nx <n && 0 <= ny && ny < n)) {
			break;
		}
		
		if (tree[nx][ny]) {
			nx += dir.x;
			ny += dir.y;
			continue;
		}
		
		for (int i = 0; i < m; i++) {
			if (runner[i][3] == 1) {
				continue;
			}
			if (nx == runner[i][0] && ny == runner[i][1]) {
				score += (t+1);
				runner[i][3] = 1;
			}
		}
		
		nx += dir.x;
		ny += dir.y;
		}
//		System.out.println(score);
	}


	private static List<Node> forward(int n) {
		List<Node> queue = new ArrayList<>();
		
		int[] dx = { -1, 0, 1, 0 };
		int[] dy = { 0, 1, 0, -1 };
		Point cur = new Point(n / 2, n / 2);
		int step = 0;
		int nx = cur.x;
		int ny = cur.y;
		out: while (true) {
			// 순방향
			for (int i = 0; i < 4; i++) {
				if (i % 2 == 0) {
					step++;
				}
				for (int j = 0; j < step; j++) {
					nx += dx[i];
					ny += dy[i];
					if (nx == 0 && ny == 0) {
						Node node = new Node(new Point(nx, ny), new Point(1, 0));
						queue.add(node);
						break out;
					}
					Node node;
					if (j == step -1) {
						node = new Node(new Point(nx, ny), new Point(dx[(i+1)%4], dy[(i+1)%4]));
					} else {
						node = new Node(new Point(nx, ny), new Point(dx[i%4], dy[i%4]));
					}
					queue.add(node);
				}
			}
		}
		
		return queue;
	}
	private static List<Node> backward(int n) {
		List<Node> queue = new ArrayList<>();
		
		int[] dx = {0, -1, 0, 1};
		int[] dy = {1, 0, -1, 0};
		Point cur = new Point(0, 0);
		int step = n;
		int nx = cur.x;
		int ny = cur.y;
		for (int i = 0; i < n - 1; i++) {
			nx += 1;
			Node node;
			if (i == n - 2) {
				node = new Node(new Point(nx, ny), new Point(0, 1));
			}
			else {				
				node = new Node(new Point(nx, ny), new Point(1, 0));
			}
			queue.add(node);
		}
		out: while (true) {
			// 순방향
			for (int i = 0; i < 4; i++) {
				if (i % 2 == 0) {
					step--;
				}
				for (int j = 0; j < step; j++) {
					nx += dx[i];
					ny += dy[i];
					if (nx == n / 2 && ny == n /2) {
						break out;
					}
					Node node;
					if (j == step -1) {
						node = new Node(new Point(nx, ny), new Point(dx[(i+1)%4], dy[(i+1)%4]));
					} else {
						node = new Node(new Point(nx, ny), new Point(dx[i%4], dy[i%4]));
					}
					queue.add(node);
				}
			}
		}
		
		return queue;
	}

}

나의 풀이

- 술래의 위치를 순방향과 역방향으로 구분하여 구한 다음 concat해주었다. 그리고 각 시간마다 시간을 index로 하여 접근하여 값을 가져왔다.

- 디버깅이 안되는 부분이 있었는데 끝점에서 예외처리하는 부분에서 방향을 바꾸어 주어야 했는데 안해주었다.

- 또한 도망자의 그 다음 위치를 구할 때 nx = x + dx[dir]을 해야 하는데 술래의 위치를 기준으로 바꾸어 주어 틀렸었다.