[Java] 격자 밟기

✔ 격자 밟기

[코드트리 격자 밟기]

문제 분석하기

A와 B의 위치를 하나씩 순서대로 옮겨가면서 모두 이동했을 때 둘이 같은 칸을 밟게 되는지 확인 

손으로 풀어보기

1. 격자 밟기 준비
2. 움직이기
   1. 격자를 벗어나지 않으면서 방문하지 않았다면 이동
   2. 모두 움직인 후 A와 B의 위치가 만난다면 가지수 증가
3. 가지수 출력하기

슈도코드 작성하기

격자 밟기 준비 {
    이동할 수 없는 칸 처리
    A 저장
    B 저장
    
    A부터 시작해 움직이기
}

움직이기 {
    if(A라면) {
        A를 움직일 수 있는지 확인하고, 움직일 수 있다면 움직인 후 다음으로 B를 움직이도록 함
    }
    if(B라면) {
        B를 움직일 수 있는지 확인하고, 움직일 수 있다면 움직임
        모두 움직였다면 A와 B의 위치가 만난다면 가지수 증가
        모두 움직이지 않았다면 다음으로 A를 움직이도록 함
    }
}

가지수 출력하기 {
    가지수 출력
}

Main {
    격자 밟기 준비
    가지수 출력하기
}

코드 구현하기

/*
 * 격자_밟기
 */
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static boolean[][] visited;
    static Person A, B;
    static int[] dr = { -1, 1, 0, 0 }; // dr, dc(상하좌우 좌표)
    static int[] dc = { 0, 0, -1, 1 };
    static int answer; // answer(가지수)

    static class Person {
        int r, c;

        public Person(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    /*
     * 1. 격자 밟기 준비
     */
    static void init(StringTokenizer st) throws IOException {
        int moveCount = 25; // moveCount(움직여야 하는 칸 수)
        visited = new boolean[5][5]; // visited(이동 유무 배열)

        int K = Integer.parseInt(st.nextToken()); // K(이동할 수 없는 칸 수)
        for (int i = 0; i < K; i++) { // 이동할 수 없는 칸 처리
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            visited[r][c] = true;
            moveCount--;
        }

        A = new Person(0, 0); // A 저장
        visited[A.r][A.c] = true;
        moveCount--;

        B = new Person(4, 4); // B 저장
        visited[B.r][B.c] = true;
        moveCount--;

        move("A", moveCount); // A부터 시작해 움직이기
    }

    /*
     * 2. 움직이기
     */
    static void move(String moveAorB, int moveCount) {
        if (moveAorB.equals("A")) {
            moveA(moveCount);
        }

        if (moveAorB.equals("B")) {
            moveB(moveCount);
        }
    }

    /*
     * A 이동
     */
    static void moveA(int moveCount) {
        int ar = A.r; // ar, ac(A의 기존 위치)
        int ac = A.c;

        for (int d = 0; d < 4; d++) {
            int anr = ar + dr[d]; // anr, anc(A의 다음 위치)
            int anc = ac + dc[d];

            if (anr < 0 || anr >= 5 || anc < 0 || anc >= 5 || visited[anr][anc]) { // 격자를 벗어났거나 방문한 곳이라면 이동 불가
                continue;
            }

            visited[anr][anc] = true;
            A.r = anr;
            A.c = anc;
            move("B", moveCount - 1); // 다음으로 B 이동

            visited[anr][anc] = false;
            A.r = ar;
            A.c = ac;
        }
    }

    /*
     * B 이동
     */
    static void moveB(int moveCount) {
        int br = B.r; // br, bc(B의 기존 위치)
        int bc = B.c;

        for (int d = 0; d < 4; d++) {
            int bnr = br + dr[d]; // bnr, bnc(B의 다음 위치)
            int bnc = bc + dc[d];

            if (bnr < 0 || bnr >= 5 || bnc < 0 || bnc >= 5) { // 격자를 벗어났다면 이동 불가 (A와 B가 만날 경우를 위해 방문한 유무는 추후 확인)
                continue;
            }

            if (moveCount == 0) { // 모두 움직인 후 A와 B의 위치가 만난다면 가지수 증가
                if (A.r == bnr && A.c == bnc) {
                    answer++;
                    return;
                } else {
                    continue; // A와 B의 위치가 만나지 않는다면 다음 방향 탐색
                }
            }

            if (visited[bnr][bnc]) { // 방문한 곳이라면 이동 불가
                continue;
            }

            visited[bnr][bnc] = true;
            B.r = bnr;
            B.c = bnc;
            move("A", moveCount - 1); // 다음으로 A 이동

            visited[bnr][bnc] = false;
            B.r = br;
            B.c = bc;
        }
    }

    /*
     * 3. 가지수 출력하기
     */
    static void print() {
        System.out.println(answer);
    }

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

        init(st);
        print();
    }
}