자바(백준) 18404 현명한 나이트

오답 노트 & 새로 알게 된 점

해당 문제는 나이트의 이동이랑 문제가 있었던 것 같은데, 

그것도 비슷한 문제이다.

 

처음에 풀 때는 참 복잡하게 풀었다.

문제에서는 입력된 상대편 말의 위치에 따라 최소 횟수를 출력하라고 했다.

그래서 나는 처음에 arr 배열을 char로 한 뒤에 K와 E를 넣고,

bfs를 돌리면서 만약에 큐에서 꺼낼 때 이게 E에 도착하면 

enemy라는 배열(출력을 입력순대로 하여 좌표를 저장함)을 처음부터 탐색하여

일치하는 것을 count배열(입력순대로 enemy와 index를 일치시켜 count를 출력하기 위함)에 저장한다.

그리고 arr배열을 '0'으로 바꿔주고 cnt++를 한다.

그리고 cnt가 M의 갯수와 같으면 반복문을 종료한다.

 

근데 풀고나보니, 그냥 처음부터 모든 배열에 최소 경로 횟수를 저장하고, 

입력순대로 그 배열 값을 출력하면 될 것 같다...

내일 다시 풀어봐야겠다.

 

원래는 정말 복잡하게 풀었는데 다시 생각하고 풀어보니 풀었던 코드의 절반 길이로 풀 수 있다.

처음부터 적들의 좌표를 순서대로 저장할 필요 없이 나이트가 존재하는 위치를 가지고

모든 cnt배열의 count갯수를 세면 된다. 문제에서 나이트가 도달할 수 있는 위치로만 주어진다고 했기 떄문이다.

이게 무슨 말이냐면 그냥 나이트의 좌표를 받는다. 그리고 cnt배열에 나이트에서부터 시작하는 bfs를 시작하여

모든 곳에 그 index에 도달하는 최소 횟수를 모두 저장한다. 그리고나서 상대편 말 정보를 입력 받은 순서대로

cnt의 index에 있는 value를 출력하면 된다.

---

 

코드1 복잡하게 푼거

package Graph;
 
import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M;
    static int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
    static int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
    static char arr[][];
    static boolean visit[][];
    static int enemy[][];
    static int count[];
    static int cnt;
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken()); //행렬 크기
        M = atoi(st.nextToken()); //적 개수
 
        arr = new char[N+1][N+1];
        visit = new boolean[N+1][N+1];
        enemy = new int[M+1][2];
        count = new int[M+1];
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                arr[i][j] = '0';
            }
        }
 
        st = new StringTokenizer(br.readLine());
 
        int x = atoi(st.nextToken());
        int y = atoi(st.nextToken());
        arr[x][y] = 'K'; //나이트 위치
 
 
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int s1 = atoi(st.nextToken());
            int s2 = atoi(st.nextToken());
            arr[s1][s2] = 'E';
            enemy[i][0] = s1;
            enemy[i][1] = s2;
        }
 
        bfs(x, y);
 
        for (int i = 1; i <= M; i++) {
            System.out.println(count[i]);
        }
    }
 
    static void bfs(int x, int y) {
        Queue<Point> q = new ArrayDeque<>();
 
        q.offer(new Point(x, y, 0));
        visit[x][y] = true;
 
        while (!q.isEmpty()) {
            Point p = q.poll();
            if (arr[p.x][p.y] == 'E') {
                for (int i = 1; i <= M; i++) {
                    if(enemy[i][0] == p.x && enemy[i][1] == p.y){
                        count[i] = p.cnt;
                        arr[p.x][p.y] = '0';
                        cnt++;
 
                    }
                }
                if(cnt == M) break;
            }
            for (int i = 0; i < 8; i++) {
                int X = p.x + dx[i];
                int Y = p.y + dy[i];
 
                if(!isRangeTrue(X,Y)) continue;
                if(visit[X][Y]) continue;
 
                q.offer(new Point(X, Y, p.cnt + 1));
                visit[X][Y] = true;
            }
        }
    }
    static boolean isRangeTrue(int x, int y) {
        return x >= 1 && x <= N && y >= 1 && y <= N;
    }
    static class Point{
        int x, y, cnt;
 
        public Point(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}
 

 

코드2 - 간단

package Graph;
 
import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M;
    static int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
    static int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
    static int arr[][];
    static boolean visit[][];
    static int cnt[][];
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        N = atoi(st.nextToken());
        M = atoi(st.nextToken()); //적의 개수
 
        st = new StringTokenizer(br.readLine());
 
        int start = atoi(st.nextToken());
        int end = atoi(st.nextToken());
 
        arr = new int[N + 1][N + 1];
        visit = new boolean[N + 1][N + 1];
        cnt = new int[N + 1][N + 1];
 
        bfs(start, end);
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s1 = atoi(st.nextToken());
            int s2 = atoi(st.nextToken());
            sb.append(cnt[s1][s2] + " ");
        }
 
        System.out.println(sb);
    }
 
    static void bfs(int x, int y) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(x);
        q.offer(y);
        visit[x][y] = true;
 
        while (!q.isEmpty()) {
            int X = q.poll();
            int Y = q.poll();
            for (int i = 0; i < 8; i++) {
                int dX = X + dx[i];
                int dY = Y + dy[i];
                if(!isRangeTrue(dX,dY)) continue;
                if(visit[dX][dY]) continue;
                q.offer(dX);
                q.offer(dY);
                visit[dX][dY] = true;
                cnt[dX][dY] = cnt[X][Y] + 1;
            }
        }
    }
 
    static boolean isRangeTrue(int x, int y) {
        return x > 0 && x <= N && y > 0 && y <= N;
    }
}