백준 16509 자바 - 장군 (BOJ 16509 JAVA)

문제 : https://www.acmicpc.net/problem/16509

 

  기본 BFS 문제다(구현이 상당히 귀찮은).

좀 덜 귀찮으려면 다음과 같이 하면 된다.

 

1. BFS 이동 위치를 문제에서 제시된 이동 위치 끝 지점만으로 한다. (코드의 dr, dc)

 

2. 이동하면서 장군에 걸리는 지점의 경우 이동이 불가하므로, 이 부분에 대한 체크 중 첫번째로 '상'의 상하좌우에 위치한 부분을 체크한다. (코드의 'switch (d)' 부분)

 

3. 다음으로 나머지 이동구간에 있는 지점들은, '1'에서 지정한 위치에서 대각선으로 한칸 이동한 위치이다. (코드의

'if (cr+dr[d]+(dr[d]<0?1:-1) == er && cc+dc[d]+(dc[d]<0?1:-1) == ec) return true;' 부분)

 

물론 그냥 직접 이동해보는게 더 안귀찮을수도 있..을 것 같은데 전 이미 늦었어요..

아무튼 저렇게 bfs 돌리면 구해진다..

 

 

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/16500/BOJ_16509.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private final static int[] dr = {2,2,3,3,-2,-2,-3,-3};
    private final static int[] dc = {-3,3,-2,2,-3,3,-2,2};

    private boolean chk(ArrayList<Integer> end, int cr, int cc, int d) {
        int er = end.get(0);
        int ec = end.get(1);
        switch (d) {
            case 0 : case 4 : if (cr==er && cc-1==ec) return true; break;
            case 1 : case 5 : if (cr==er && cc+1==ec) return true; break;
            case 2 : case 3 : if (cr+1==er && cc==ec) return true; break;
            case 6 : case 7 : if (cr-1==er && cc==ec) return true; break;
        }
        if (cr+dr[d]+(dr[d]<0?1:-1) == er && cc+dc[d]+(dc[d]<0?1:-1) == ec) return true;
        return false;
    }

    private int bfs(ArrayList<Integer> start, ArrayList<Integer> end) {
        int[][] dist = new int[10][9];
        for (int i = 0; i < dist.length; i++)
            Arrays.fill(dist[i], -1);

        Queue<ArrayList<Integer>> q = new ArrayDeque<>();
        q.add(start);
        dist[start.get(0)][start.get(1)] = 0;
        while (!q.isEmpty()) {
            int cr = q.peek().get(0);
            int cc = q.poll().get(1);
            if (end.get(0) == cr && end.get(1) == cc) {
                return dist[cr][cc];
            }
            for (int d = 0; d < 8; d++) {
                int nr = cr+dr[d];
                int nc = cc+dc[d];
                if (nr<0||nr>=10||nc<0||nc>=9||dist[nr][nc]!=-1||chk(end, cr, cc, d)) continue;
                ArrayList<Integer> next = new ArrayList<>();
                next.add(nr);
                next.add(nc);
                dist[nr][nc] = dist[cr][cc]+1;
                q.add(next);
            }
        }

        return -1;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Integer> start = new ArrayList<>(2);
        start.add(Integer.parseInt(st.nextToken()));
        start.add(Integer.parseInt(st.nextToken()));

        st = new StringTokenizer(br.readLine());
        ArrayList<Integer> end = new ArrayList<>(2);
        end.add(Integer.parseInt(st.nextToken()));
        end.add(Integer.parseInt(st.nextToken()));

        System.out.println(bfs(start, end));
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}