백준 5213 : 과외맨

https://www.acmicpc.net/problem/5213

5213번: 과외맨

[ 문제풀이 ]

지문이 굉장히 길어서 이해하는데 조금 시간이 걸렸지만 결국 1번 타일부터 시작하여 각 타일들을 통해 이동할 수 있는 타일 중 번호가 가장 큰 타일의 최소 경로를 찾아주면 되는 문제이다.

이동할 수 있는 타일 간의 거리는 1이기 때문에 BFS를 수행해주면 된다. 다만, 각 타일마다 이동할 수 있는 경로를 어떻게 설정해줄 것인지가 문제이다.

기본적으로 타일이 이동할 수 있는 경로는 6개이다. 하지만 각 층마다 모서리에 있는 타일들은 이동할 수 있는 경로가 제한된다.

이는 홀수 층의 좌우측 타일, 짝수 층의 좌우측 타일, 나머지 타일, 총 5가지 타입의 타일이 존재한다. 또한, 우측의 타일은 현재 타일의 right 값과 동일할 때 이동할 수 있으며, 좌측의 타일은 현재 타일의 left 값과 동일할때 이동할 수 있다.

따라서 타일들을 입력받을때 총 5가지 타입에 따라 타일을 배정해줘서 bfs를 수행할때 이동할 수 있도록 구현해준다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	static class Node {
		int idx, left, right, flag, move;

		/**
		 * @param flag : 타일의 위치, 0=나머지/1=홀수 좌측/2=홀수 우측/3=짝수 좌측/4=짝수 우측
		 */
		public Node(int idx, int left, int right, int flag, int move) {
			this.idx = idx;
			this.left = left;
			this.right = right;
			this.flag = flag;
			this.move = move;
		}
	}

	static final int INF = (int)1e9;
	static int N, size;
	static Node[] node;
	static int[] dist, path;
	static boolean[] visit;
	static Stack<Integer> stack;
	static int[][] dir;

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))){
			N = Integer.parseInt(br.readLine());
			size = N * N - N / 2;
			node = new Node[size + 1];
			visit = new boolean[size + 1];
			dist = new int[size + 1];
			path = new int[size + 1];
			/**
			 *  -N(5)  -N+1(0)
			 *-1(4)  idx   1(1)
			 *  N-1(3)   N(2)   
			 */
			dir = new int[][] {{-N+1, 1, N, N-1, -1, -N},
				{-N+1, 1, N},
				{0, 0, 0, N-1, -1, -N},
				{-N+1, 1, N, N-1, 0, -N},
				{-N+1, 0, N, N-1, -1, -N}
			};
			stack = new Stack<>();

			int level = 1, cnt = 0, left = 1, right = N;
			for (int i = 1; i <= size; ++i) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int A = Integer.parseInt(st.nextToken());
				int B = Integer.parseInt(st.nextToken());

				cnt++;
				if (level % 2 == 1) {
					if (i == left) node[i] = new Node(i, A, B, 1, 1);
					else if (i == right) node[i] = new Node(i, A, B, 2, 1);
					else node[i] = new Node(i, A, B, 0, 1);

					if (cnt % N == 0) {
						level++;
						cnt = 0;
						left += N;
						right += N - 1;
					}
				} else {
					if (i == left) node[i] = new Node(i, A, B, 3, 1);
					else if (i == right) node[i] = new Node(i, A, B, 4, 1);
					else node[i] = new Node(i, A, B, 0, 1);

					if (cnt % (N - 1) == 0) {
						level++;
						cnt = 0;
						left += N - 1;
						right += N;
					}
				}
			}

			bfs();

			for (int i = size; i >= 1; --i) {
				if (dist[i] != INF) {
					bw.write(dist[i] + "\n");
					getPath(i);
					while (!stack.isEmpty()) {
						bw.write(stack.pop() + " ");
					}
					break;
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public static void bfs() {
		Arrays.fill(dist, INF);
		Queue<Node> q = new LinkedList<>();
		q.offer(node[1]);
		dist[1] = 1;
		visit[1] = true;

		while (!q.isEmpty()) {
			Node n = q.poll();

			for (int i = 0; i < dir[n.flag].length; ++i) {
				if (dir[n.flag][i] == 0) continue;

				int nv = n.idx + dir[n.flag][i];

				if (nv <= 0 || nv > size || visit[nv]) continue;
				if (i <= 2) {
					if (n.right != node[nv].left) continue;
				} else {
					if (n.left != node[nv].right) continue;
				}

				visit[nv] = true;
				dist[nv] = n.move + 1;
				path[nv] = n.idx;
				q.offer(new Node(nv, node[nv].left, node[nv].right, node[nv].flag, n.move + 1));
			}
		}
	}

	public static void getPath(int v) {
		if (v == 0) return;
		stack.add(v);
		getPath(path[v]);
	}
}