[백준 17070번] 파이프 옮기기 1

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

 

package graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Graph17070 {

    static class From {
        int x;
        int y;

        public From(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static class To {
        int x;
        int y;

        public To(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static class Node {
        From from;
        To to;

        public Node(From from, To to) {
            this.from = from;
            this.to = to;
        }
    }

    static int N;

    static int count = 0;
    static int[][] map;

    static int[] dx = {1, 0, 1};
    static int[] dy = {0, 1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        if (!(map[N - 1][N - 1] == 1)) {
            bfs();
        }

        if (count != 0) {
            System.out.println(count);
        } else {
            System.out.println(0);
        }
    }

    static void bfs() {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(new From(1, 1), new To(1, 2)));

        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            From from = poll.from;
            To to = poll.to;

            // 가로, 세로, 대각선 인지 검토
            if (to.x - from.x == 0 && to.y - from.y == 1) {
                question1(queue, to, 1);
                question2(queue, to);

            } else if (to.x - from.x == 1 && to.y - from.y == 0) {
                question1(queue, to, 0);
                question2(queue, to);
            } else {
                question1(queue, to, 1);
                question1(queue, to, 0);
                question2(queue, to);
            }

        }


    }


    // 가로 및 세로
    static void question1(Queue queue, To to, int k) {
        int nextX = to.x + dx[k];
        int nextY = to.y + dy[k];
        if (nextX - 1 < N && nextY - 1 < N && nextX - 1 >= 0 && nextY - 1 >= 0) {
            if (map[nextX - 1][nextY - 1] == 0) {
                queue.add(new Node(new From(to.x, to.y), new To(nextX, nextY)));
                if (nextX == N && nextY == N) {
                    count++;
                }
            }

        }
    }

    // 대각선
    static void question2(Queue queue, To to) {
        int nextX = to.x + dx[2];
        int nextY = to.y + dy[2];
        if (nextX - 1 < N && nextY - 1 < N && nextX - 1 >= 0 && nextY - 1 >= 0) {
            if (map[nextX - 1][nextY - 1] == 0 && map[nextX - 1][nextY - 2] == 0 && map[nextX - 2][nextY - 1] == 0) {
                queue.add(new Node(new From(to.x, to.y), new To(nextX, nextY)));
                if (nextX == N && nextY == N) {
                     count++;
                }
            }

        }
    }
}

 

 

이론적으로 정리한 내용을 코드로 차근차근 실행해보니 맞았다! 문제의 핵심은 가로일 때는 가로로, 세로일 때는 세로로 이동하며, 동시에 대각선 이동도 가능하다는 점이다. 또한, 대각선 상태에서는 가로, 세로, 대각선 세 가지 방향으로 이동할 수 있다. 이때 대각선으로 이동하려면 공간을 3개 차지하게 되므로, 해당 위치에 1이 있는 경우는 제외해야 한다. 관리의 편의성을 위해 객체를 활용하여 구현했다.

하지만 필자가 마지막 도착지점이 1일때 그리고 if문을 잘못 써서 오류를 잡기 좀 애먹었다.