[BOJ - JAVA] 17129 - 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유(BFS)

# 주소

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

17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

# 문제 

# 문제 해설 및 코드 리뷰

import java.util.*;
class Main{
    static class Point{
        int x;
        int y;
        int time;
        Point(int x, int y, int time){
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }
    static int n, m;
    static int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    static int[][] arr;
    static int min = Integer.MAX_VALUE;
    static boolean[][] visit;
    static Queue<Point> queue = new LinkedList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n][m];
        visit = new boolean[n][m];
        for(int i = 0; i < n; i++) {
            String str = scan.next();
            for (int j = 0; j < m; j++) {
                arr[i][j] = str.charAt(j) - '0';
                if (arr[i][j] == 2) {
                    queue.offer(new Point(i, j, 0));
                    visit[i][j] = true;
                }
            }
        }
        bfs();
        if(min == Integer.MAX_VALUE)
            System.out.println("NIE");
        else {
            System.out.println("TAK");
            System.out.println(min);
        }
    }
    static void bfs(){
        while (!queue.isEmpty()) {
            Point now = queue.poll();
            if(arr[now.x][now.y] == 3 || arr[now.x][now.y] == 4 || arr[now.x][now.y] == 5){
                min = now.time;
                break;
            }
            for(int i = 0; i < 4; i++){
                int nx = now.x + dir[i][0];
                int ny = now.y + dir[i][1];
                if(nx < 0 || ny < 0 || nx >= n || ny >= m)
                    continue;
                if(visit[nx][ny])
                    continue;
                if(arr[nx][ny] == 1)
                    continue;
                queue.offer(new Point(nx, ny, now.time + 1));
                visit[nx][ny] = true;
            }
        }
    }
}

이 문제도 간단한 BFS문제입니다.

2의 위치에서 3 또는 4 또는 5의 위치에 도달했을 때 그때의 최소 횟수를 구하는 문제입니다.

그래서 해당 인덱스에 도달할 수 있으면 TAK을 출력하고 그 때의 이동 거리를

그리고 해당 인덱스에 도달할 수 없으면 NIE를 출력하고 끝내면 되겠습니다.

이 문제가 어려우시면 이전의 포스트들을 차차 보시면 진짜 별거 아니라고 느끼실거에요.

골드문제들을 풀어보고 있는데 아마 골드 그래프 탐색 문제중 제일 쉽지 않을까 싶습니다.

감사합니다.