[백준/JAVA] 16509번: 장군

📖 문제

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

 

 

💡  풀이 방식

• BFS

 

필요 자료구조
- 상하좌우 이동용 dx/dy배열
- 대각선 이동용 cx/cy 배열
- 탐색 위한 BFS용 큐
- 좌표 방문 표시용 2차원 boolean형 배열

 

 

상 위치에서부터 BFS를 시작해 왕에게 도달하는 횟수를 구한다.

- 만약 현재 큐에서 뽑은 위치값이 왕의 위치와 같다면, 여태 구한 이동 횟수를 출력한다.

- 그렇지 않다면, 경로가 막혔는지 판단하며 탐색을 진행한다.

   ㄴ 먼저 상하좌우 방향으로 한 칸 이동한다.

   ㄴ 마저 이동 가능한 경우, 상하좌우 움직임에 따라 방향을 2개씩 매칭한 후 해당 방향으로 확산시키며 이동 횟수를 갱신한다.

// 경로가 막혀있는지 판단용 함수
private static void check(Node n) {
    for(int d = 0 ; d < 4 ; d++) {  // 상하좌우
        // 1) 일단 상하좌우 방향으로 한 칸 이동
        int tx = n.x + dx[d];
        int ty = n.y + dy[d];

        if(isPossible(tx, ty)) {
            // 2) 상하좌우 움직임에 따라 방향 2개씩 매칭
            for(int cnt = 0; cnt < 2 ; cnt++) {
                int s = (d + cnt) % 4;
                int nx = tx + cx[s];
                int ny = ty + cy[s];

                if(isPossible(nx, ny)) {
                    nx += cx[s];
                    ny += cy[s];

                    if(inRange(nx, ny) && !visited[nx][ny]) {	// 해당 위치 큐에 추가해 마저 탐색
                        visited[nx][ny] = true;
                        q.add(new Node(nx, ny, n.step + 1));
                    }
                }
            }
        }
    }
}

// 이동 가능한지 판별하는 함수
private static boolean isPossible(int x, int y) {
    if(x == kr && y == kc)  // 킹 마주치면 이동 불가
        return false;
    return inRange(x, y);
}

 

 

 

💥 유의사항

- 격자 범위 벗어나지 않는지 확인

- 대각선 이동할 때 마저 잘 확인

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0,1,0,-1}; // 동남서북
    static int[] dy = {1,0,-1,0};
    
    static int[] cx = {-1, 1, 1, -1};   // 대각선
    static int[] cy = {1, 1, -1, -1};
    
    static int kr,kc;
    
    static Queue<Node> q = new ArrayDeque<>();
    static boolean[][] visited = new boolean[10][9];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] str1 = br.readLine().split(" ");
        int sr = Integer.parseInt(str1[0]);
        int sc = Integer.parseInt(str1[1]);
        visited[sr][sc] = true;
        q.add(new Node(sr, sc, 0));
        
        String[] str2 = br.readLine().split(" ");
        kr = Integer.parseInt(str2[0]);
        kc = Integer.parseInt(str2[1]);
        
        System.out.println(bfs());
    }
    
    private static int bfs() {
        while(!q.isEmpty()) {
            Node now = q.poll();
            
            if(now.x == kr && now.y == kc) { // 킹 마주치면 종료
                return now.step;
            }
            
            check(now);
        }
        return -1;
    }
    
    // 경로가 막혀있는지 판단용 함수
    private static void check(Node n) {
        for(int d = 0 ; d < 4 ; d++) {  // 상하좌우
            // 일단 상하좌우 방향으로 한 칸 이동
            int tx = n.x + dx[d];
            int ty = n.y + dy[d];
            
            if(isPossible(tx, ty)) {
                // 상하좌우 움직임에 따라 방향 2개씩 매칭
                for(int cnt = 0; cnt < 2 ; cnt++) {
                    int s = (d + cnt) % 4;
                    int nx = tx + cx[s];
                    int ny = ty + cy[s];
                    
                    if(isPossible(nx, ny)) {
                        nx += cx[s];
                        ny += cy[s];
                        
                        if(inRange(nx, ny) && !visited[nx][ny]) {
                            visited[nx][ny] = true;
                            q.add(new Node(nx, ny, n.step + 1));
                        }
                    }
                }
            }
        }
    }
    
    // 이동 가능한지 판별하는 함수
    private static boolean isPossible(int x, int y) {
        if(x == kr && y == kc)  // 킹 마주치면 이동 불가
            return false;
        return inRange(x, y);
    }
    
    // 격자 범위 내에 있는지 확인하는 함수
    private static boolean inRange(int x, int y) {
        return 0 <= x && x < 10 && 0 <= y && y < 9;
    }
}
 
class Node {
    int x,y,step;
    
    public Node(int x, int y, int step) {
        this.x = x;
        this.y = y;
        this.step = step;
    }
}
 

 

 

 

➕ 다른 풀이 방식

- 대각선 8방향 다 저장해서 푼 분도 계셨다.

[Baekjoon] 16509_장군

---

💦 어려웠던 점

- 각 상하좌우에 대한 대각선 방향을 어떻게 처리해줘야하지?의 문제

- 2칸 중에 1칸 이동하다가 이동 못하고 걸리면 어떻게 해야하지?의 문제

 

🧐 새로 알게 된 내용

- dx/dy배열을 순서에 맞게 잘 의도하여 작성해두면 방향 설정할 때 편하다.

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[ 백준 16509 ] 장군 (Java)