[자바, Java] 백준 31575: 도시와 비트코인

문제

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

31575번: 도시와 비트코인

코드

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

public class Main {

    static int n;
    static int m;
    static int[][] city;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        city = new int[m][n];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < n; j++) {
                city[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        if (bfs()) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    private static boolean bfs() {
        visited = new boolean[m][n];

        int[] dx = {1, 0};
        int[] dy = {0, 1};

        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        visited[0][0] = true;

        while (!q.isEmpty()) {
            int[] nums = q.poll();
            int x = nums[1];
            int y = nums[0];

            for (int i = 0; i < 2; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (0 <= nx && 0 <= ny && nx < n && ny < m && !visited[ny][nx] && city[ny][nx] == 1) {
                    visited[ny][nx] = true;
                    q.add(new int[]{ny, nx});
                }
            }
        }
        return visited[m - 1][n - 1];
    }
}

설명

자바로 코테를 연습할 일이 생겨서 오래간만에 BFS 문제를 풀어보았다.

흔한 BFS 문제였는데 동쪽과 남쪽으로만 이동한다는 조건을 놓쳐서 잠시 헤맨 문제였다.
n과 m의 입력도 반대로 주어져서 주의를 해야하는 문제다.

우선 입력값을 받아주고 도시 정보를 세팅해준다.

그리고 bfs를 실행하는데, 움직일 수 있는 방향이 동쪽과 남쪽이므로 이동할 수 있는 dx, dy를 해당 좌표로 설정을 해준다.

이후에 큐에 시작 좌표를 넣고 탐색을 하며 visited 값을 체크해 준다.

이후 visited 좌표에 따라 결과를 출력한다.