[BOJ][Java] 백준 11084번: 나이트의 염탐

1일 1PS 26일차!

📚 문제

---

골드 2

• visited 와 함께 bfs 를 진행한다.

• 이동 방법을 카운팅하기 위해 dp 를 사용한다.

  • 이때 방법은 모두 더해주고 visited 되었다면 다음 queue 에 add 하지 않는다.

• “틀렸습니다” 포인트.. 생각보다 쓸데없이 시간을 많이 소비했다..

  • 한번이라도 목적지에 도착하면 목적지에 도착하는 방법은 어짜피 dp[r-3][c-2], dp[r-2][c-3] 이기 때문에 그냥 더해줬지만 (2,3) 같은 경우에 outOfIndex 가 발생한다.
  • % 1000000009 를 해줘야한다. dp가 더해지는 모든 순간에 해줘야한다.
  • dp[nx][ny] += dp[temp[0]][temp[1]] % 1000000009; 이렇게 했는데 %의 연산자 순위가 더 높기 때문에 dp 가 1000000009 보다 커질 수 있다.
  • (1,1) 이 입력되었을 때 None 이 아니라 “0 1” 이 출력되어야한다. 그냥 예외처리만 해줬다.
• 위의 틀린 경우 그냥 예외처리 해버려서 코드가 좀 더러워졌다.

💡 포인트

---

1. direction 을 8방면으로 저장한다.
2. bfs 를 진행하면서 visited 된 곳은 queue 에 집어넣지 않고 카운팅 횟수만 더한다.

💻 코드

---

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 n11084 {
    static boolean[][] visited;
    static int[][] dp;
    static int[][] dir = {{2, 1}, {2, -1}, {1, 2}, {1, -2}, {-2, 1}, {-2, -1}, {-1, 2}, {-1, -2}};
    static Queue<int[]> queue;

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

        queue = new LinkedList<>();

        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        visited = new boolean[r][c];
        dp = new int[r][c];

        if (r == 1 & c == 1){
            System.out.println("0 1");
            return;
        }


        int cnt = bfs(r, c);

        if (cnt == -1){
            System.out.println("None");
        } else {
            int num = 0;
            if (r-3 >= 0 & c-2 >= 0){
                num += dp[r - 3][c - 2];
            }
            if (r-2 >= 0 & c-3 >= 0){
                num += dp[r - 2][c - 3];
            }
            num = num % 1000000009;
            System.out.println(cnt + " " + num);
        }
    }

    private static int bfs(int r, int c) {
        queue.add(new int[]{0, 0, 1});
        dp[0][0] = 1;
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            int nx, ny;
            for (int i = 0; i < 8; i++) {
                nx = temp[0] + dir[i][0];
                ny = temp[1] + dir[i][1];

                if (nx < 0 | ny < 0 | nx >= r | ny >= c) {
                    continue;
                }
                if (nx == r - 1 & ny == c - 1) {
                    return temp[2];
                }
                dp[nx][ny] = (dp[nx][ny] + dp[temp[0]][temp[1]]) % 1000000009;

                if(!visited[nx][ny]){
                    queue.add(new int[]{nx, ny, temp[2]+1});
                    visited[nx][ny] = true;
                }
            }
        }
        return -1;
    }
}