[Algorithm] 백준 2178, 1697 BFS 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 BFS에서 비슷한 문제인 백준 2178, 1697번의 자바 풀이를 작성하고자 합니다.

BFS는 Queue를 활용하기 때문에 선입 선출로 처리되며 최단 거리를 찾는데 효율적입니다.

 

문제 링크: https://www.acmicpc.net/problem/2178

문제 링크: https://www.acmicpc.net/problem/1697

 

코드와 주석으로 먼저 제시한 후, 중요한 포인트를 작성하도록 하겠습니다.!

 

1. 코드 

 

<Boj2178>

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

import java.util.Queue;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

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

        int n = getInt(st);
        int m = getInt(st);
        Maze maze = new Maze(n, m); // 미로 인스턴스 생성

        String str;
        for (int i = 0; i < n; i++) {
            str = br.readLine();
            for (int j = 0; j < m; j++) {
                maze.setInit(i, j, Character.getNumericValue(str.charAt(j))); // 미로의 1 혹은 0 입력
            }
        }

        maze.findDestination(); // 미로 목적지 찾기 메서드
        maze.printStep(); // 정답을 찾기 위한 깊이를 출력
    }

    static int getInt(StringTokenizer st) {
        return parseInt(st.nextToken());
    }
}

class Maze {

    static int[] D_X = {1, 0, -1, 0}; // 좌표
    static int[] D_Y = {0, 1, 0, -1};
    Room[][] rooms; // 미로의 방 이차원 배열

    class Room {
        int x; // x 좌표
        int y; // y 좌표
        int step; // 큐에 들어 간 깊이 
        int num; // 1 or 0
        boolean visited; // 방문 여부

        Room (int x, int y, int num) {
            this.x = x;
            this.y = y;
            this.num = num;
        }
    }

    Maze(int n, int m) {
        rooms = new Room[n][m]; // 생성자로 방의 이차원 배열 생성
    }

    void setInit(int x, int y, int num) {
        rooms[x][y] = new Room(x, y, num); // 배열의 좌표와 숫자로 초기화
    }

    void findDestination() {
        Queue<Room> queue = new ArrayDeque<>(); // queue 생성
        rooms[0][0].visited = true; // 0, 0 좌표 방문 처리
        rooms[0][0].step = 1; // 0, 0 좌표 단계 설정
        queue.add(rooms[0][0]); // 큐 추가
        bfs(queue); // bfs 호출
    }

    void bfs(Queue<Room> queue) {

        while (!queue.isEmpty()) { // queue가 빌 때 까지 반복
            Room room = queue.poll(); // queue에서 room 빼기

            if ((room.x == rooms.length - 1) && (room.y == rooms[0].length - 1)) {
                break; // 만약 마지막 위치에 도달한다면 반복문 종료
            }

            for (int k = 0; k < 4; k++) {
                int newX = D_X[k] + room.x;
                int newY = D_Y[k] + room.y;
                if (validRange(newX, newY)) {
                    rooms[newX][newY].visited = true; // 방문 여부 등록
                    rooms[newX][newY].step = room.step + 1; // queue에 등록된 부모 노드의 깊이 + 1
                    queue.add(rooms[newX][newY]); // 큐 등록
                }
            }
        }

    }

    void printStep() {
        System.out.println(rooms[rooms.length - 1][rooms[0].length - 1].step);
    }


    boolean validRange(int x, int y) {
        return x >= 0 && y >= 0 && x < rooms.length && y < rooms[0].length &&
                !rooms[x][y].visited && rooms[x][y].num == 1;
    }
}

 

<Boj1697>

 

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

import java.util.StringTokenizer;
import java.util.Queue;
import java.util.ArrayDeque;

import static java.lang.Integer.parseInt;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = parseInt(st.nextToken());
        int k = parseInt(st.nextToken());

        HideAndSeek hideAndSeek = new HideAndSeek(n, k);
        hideAndSeek.findTime();
        hideAndSeek.printTime();
    }
}

class HideAndSeek {

    static final int MAX_DISTANCE = 100001; // 최대 거리 (0, 10만 일 경우)
    Location[] locations = new Location[MAX_DISTANCE];

    int n; // 수빈 위치
    int k; // 동생 위치

    class Location {
        int x; // 위치 좌표
        int t; // 걸린 시간
        boolean visited; // 방문 여부

        Location(int x) {
            this.x = x;
        }
    }

    HideAndSeek(int n, int k) { // 생성자로 Location[] 배열에 location 등록
        this.n = n;
        this.k = k;
        for (int i = 0; i < MAX_DISTANCE; i++) locations[i] = new Location(i);
    }

    void findTime() {
        Queue<Location> queue = new ArrayDeque<>();
        locations[n].visited = true;
        queue.add(locations[n]); // 먼저 수빈 위치의 인스턴스를 큐에 등록
        bfs(queue); // bfs 시작
    }

    void bfs(Queue<Location> queue) {
        int d;
        while(!queue.isEmpty()) {
            Location location = queue.poll(); // 큐에 있는 location 인스턴스 추출

            if (location.x == k) break; // 만약 시간이 같다면 break;

            d = location.x;
            int[] dx = {d + 1, d - 1, d * 2};

            // 만약 현재 위치에서 dx만큼 변한 것이 0보다 크고, 최대 거리를 넘지 않고, 방문 X라면
            for (int z : dx) {
                if (z >= 0 && z < MAX_DISTANCE && !locations[z].visited) {
                    locations[z].visited = true;
                    locations[z].t = location.t + 1; // 다음에 탐색할 location의 시간을 1 추가
                    queue.add(locations[z]);
                }
            }
        }
    }

    void printTime() {
        System.out.println(locations[k].t);
    }
}

 

1697번은 수빈과 동생의 위치를 x로 놓은 후, 우리가 찾아야 하는 t를 step으로 설정합니다!

 

 

2. Queue로 BFS를 구현할 때, step 처리 반드시 설정하기!

 

void bfs(Queue<Room> queue) {

    while (!queue.isEmpty()) {
        Room room = queue.poll();

        if ((room.x == rooms.length - 1) && (room.y == rooms[0].length - 1)) {
            break;
        }

        for (int k = 0; k < 4; k++) {
            int newX = D_X[k] + room.x;
            int newY = D_Y[k] + room.y;
            if (validRange(newX, newY)) {
                rooms[newX][newY].visited = true;
                rooms[newX][newY].step = room.step + 1;
                queue.add(rooms[newX][newY]);
            }
        }
    }
}

 

이 문제는 얼마나 최단 거리로 도착할 수 있는가를 찾는 문제이므로 노드를 삽입한 부모 노드의 깊이에 1을 더하는 것이 중요합니다.

 

BFS는 

1 -> 2 -> 3 순서로 Queue에 넣고 poll하면, 1번 노드가 출력이 되고 1번 노드에 인접한 4, 5 번을 queue에 넣고,

2번 노드를 빼서 인접한 노드 6, 7을 넣게 되면 남은 노드의 처리 순서는 3 -> 4 -> 5 -> 6 -> 7 입니다.

이때, 중요한 점이, 4 5 6 7 의 부모 노드가 무엇인지 모를 수 있으므로 깊이 처리가 어려울 수 있습니다.

따라서, 큐에 등록할 때, 부모 노드 깊이 + 1를 설정해야 큐에서 노드를 뺐을 때, 해당 노드의 깊이를 파악할 수 있습니다.!

그리고, 이 깊이가 바로 최단 거리에 해당하는 답인 것입니다.!

 

이상으로 2178, 1697번의 BFS 문제 정리를 마치도록 하겠습니다.! 감사합니다!