백준 : 5213 JAVA

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

5213번: 과외맨

문제를 푸는데 작은 부분에서 많이 해매었던 문제다.

도미노 판을 표시하는 Map과 각각의 도미노의 번호를 표시하는 맵을 만들면된다.

물론 도미노의 크기는 1*2 크기이므로 Map도 Map[N][N*2] 가 만들어져야한다.

받을 때는 홀수와 짝수행에 신경을 써야한다. 그러면 지그재그로는 어떻게 놔둘것인가 ??

0이라는 값은 비어잇는 공간처럼 사용하면된다 마침 도미노의 크기는 1부터 시작된다.

이렇게 놔두면 BFS를 이용해서 사방 탐색을 할수가 있다.

여기서 내가 생각을 짧게한 실수는 봐로 운선위큐를 활용해서 Cnt 움직인 횟수에 간한 값을 q에 넣어주면

만약 1이라는 도미노는 left right로 구분된다.  이때 q에 left만 들어와잇을 때 right로 가는 값은 경로에 표시하면 안된다. 나는 우선순위 큐를 사용하면 left 큐를 처리하고 right큐를 바로처리한다고 차각햇다 .. 

하지만 right큐는 다른 q를 처리하고 오는 경우가 있으므로 경로가 이상하게 쌓일수가 있다.

따라서 도미노는 하나의 큐에 두값을 동시에 넣어야 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class B5213 {
    static int N;
    static int E;
    static int map[][];
    static int p[][];
    static int rought[];
 
    static int dy[] = { 1, -1, 0, 0 };
    static int dx[] = { 0, 0, 1, -1 };
 
    static class Pair {
        int y;
        int x;
 
        public Pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        map = new int[N][N * 2];
        p = new int[N][N * 2];
        rought = new int[N * N - N / 2 + 1];
        int num = 1;
        int start = 0;
        for (int i = 0; i < N; i++) {
            int e = i % 2 == 0 ? N : N - 1;
            int j = i % 2 == 0 ? 0 : 1;
 
            for (int ee = 0; ee < e; ee++) {
                st = new StringTokenizer(br.readLine());
                p[i][j] = num;
                map[i][j++] = Integer.parseInt(st.nextToken());
                p[i][j] = num++;
                map[i][j++] = Integer.parseInt(st.nextToken());
 
            }
        }
 
        boolean visit[][] = new boolean[N][N * 2];
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(0, 0));
        q.add(new Pair(0, 1));
        visit[0][0] = true;
        visit[0][1] = true;
 
        while (!q.isEmpty()) {
            Pair cur = q.poll();
            if (p[cur.y][cur.x] > start) {
                start = p[cur.y][cur.x];
            }
 
            if (cur.y == N - 1 && cur.x == N * 2 - 2) {
                break;
            }
 
            int y = cur.y;
            int x = cur.x;
            for (int d = 0; d < 4; d++) {
                int ny = y + dy[d];
                int nx = x + dx[d];
                if (ny < 0 || nx < 0 || ny >= N || nx >= N * 2)
                    continue;
                if (visit[ny][nx])
                    continue;
                if (p[ny][nx] == 0)
                    continue;
                if (map[y][x] != map[ny][nx])
                    continue;
                int nnx = 0;
                if (ny % 2 == 0) {
                    if (nx % 2 == 0) {
                        nnx = nx + 1;
                    } else {
                        nnx = nx - 1;
                    }
                } else {
                    if (nx % 2 == 0) {
                        nnx = nx - 1;
                    } else {
                        nnx = nx + 1;
                    }
                }
 
                visit[ny][nx] = true;
                visit[ny][nnx] = true;
                q.add(new Pair(ny,nnx));
                q.add(new Pair(ny, nx));
 
                rought[p[ny][nx]] = p[y][x];
            }
 
        }
 
        Stack<Integer> stack = new Stack<Integer>();
 
        stack.add(start);
        while (start != 1) {
            start = rought[start];
            stack.add(start);
        }
        StringBuilder sb = new StringBuilder();
        sb.append(stack.size()).append('\n');
 
        sb.append(stack.pop());
        while (!stack.isEmpty()) {
            sb.append(' ').append(stack.pop());
        }
 
        System.out.print(sb.toString());
    }
 
}