[DFS/자바] 코드트리 실력진단. 나이트

문제는 비공개이기 때문에 첨부하지 않겠다.

 

문제 해석

이 문제는 체스 나이트의 이동 패턴을 이용하여 나이트가 어디어디 갈 수 있는지 파악하는 문제였다. 2차원 격자 위에서 움직이는 패턴이 일정하므로 인접한 좌표로 이동할 수 있는 그래프 탐색 알고리즘을 사용하면 될 것이라고 생각했고, 전체를 탐색해야 하는 것이지 최단거리를 알아낼 필요는 없으므로 상대적으로 구현이 더 단순한 DFS를 사용하는 것이 효율적일 것이라고 판단하였다.

 

문제에서 요구하는 출력 결과는 visited 배열값을 이용하면 파악할 수 있을 것이라고 판단하였다.

 

문제 풀이

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

public class Main {
    private static int n;
    private static int[][] arr;
    private static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        arr = new int[n][n];
        visited = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        st = new StringTokenizer(br.readLine());
        int startY = Integer.parseInt(st.nextToken())-1;
        int startX = Integer.parseInt(st.nextToken())-1;
        visited[startY][startX] = true;
        dfs(new Pair(startY, startX));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] == 1) {
                    System.out.print(0 + " ");
                } else if (visited[i][j]) {
                    System.out.print(1 + " ");
                } else {
                    System.out.print(0 + " ");
                }
            }
            System.out.println();
        }
    }

    private static void dfs(Pair crt) {
        int[] dx = new int[]{1, 2, 2, 1, -1, -2, -2, -1};
        int[] dy = new int[]{-2, -1, 1, 2, 2, 1, -1, -2};

        for (int i = 0; i < 8; i++) {
            int newY = crt.y + dy[i];
            int newX = crt.x + dx[i];
            if (canGo(newY, newX)) {
                visited[newY][newX] = true;
                dfs(new Pair(newY, newX));
            }
        }
    }

    private static boolean canGo(int y, int x) {
        return inRange(y, x) && arr[y][x] == 0 && !visited[y][x];
    }

    private static boolean inRange(int y, int x) {
        return y >= 0 && y < n && x >= 0 && x < n;
    }

    private static class Pair {
        private int x, y;

        private Pair(int y, int x) {
            this.x = x;
            this.y = y;
        }
    }

}