[코드트리/INTERMEDIATE LOW] 갈 수 있는 곳들 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

💡  풀이 방식

• BFS

1. 격자를 입력받는다.

2. 시작점을 K번 입력받는다.

  - 입력받은 시작점에서 BFS를 수행해 현재 시작점에서 도달 가능한 칸 수를 구하고, 정답에 이를 누적해 더한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
 
    static int N, K;
    static int[][] grid;    // int형 배열
    static int[][] visited; // 방문 배열 (boolean형으로 해도 됨)
 
    static int ans = 0;
 
    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());
        K = Integer.parseInt(st.nextToken());
 
        grid = new int[N + 1][N + 1];
        visited = new int[N + 1][N + 1];
 
        for(int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 1 ; j <= N ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        while(K --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
 
            ans += bfs(r, c);
        }
 
        System.out.println(ans);
    }
 
    private static int bfs(int x, int y) {
        // 이미 방문한 적 있는 칸이라면 pass
        if(visited[x][y] == 1) {
            return 0;
        }
 
        Queue<int[]> q = new ArrayDeque<>();    // 칸 위치 저장할 큐
        q.add(new int[] {x, y});
 
        visited[x][y] = 1;  // 방문 처리
 
        int cnt = 1;    // 도달 가능한 칸 수
 
        while(!q.isEmpty()) {
            int[] now = q.poll();
 
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
 
                // 방문 가능한 칸이라면 > 방문 처리하고, 도달 가능한 칸 수 갱신하고, 큐에 위치 추가
                if(canGo(nx, ny)) {
                    visited[nx][ny] = 1;    
                    cnt++;        
                    q.add(new int[] {nx, ny});
                }
            }
        }
 
        return cnt;
    }
 
    private static boolean canGo(int x, int y) {
        if(!inRange(x, y))  return false;
        if(visited[x][y] == 1 || grid[x][y] == 1) return false;
        return true;
    }
 
    private static boolean inRange(int x, int y) {
        return (1 <= x && x <= N && 1 <= y && y <= N);
    }
}

 

 

---

💦 어려웠던 점

시작 지점으로부터 방문 가능한 "서로 다른" 칸 개수라 해서 2차원 int형 방문 배열을 만들어 방문 횟수가 1인 애들만 출력하려고 했었다. 그런데 그럴 필요가 없었고, 그냥 한 번 방문한 칸은 다시 방문하지 않도록 하면 되는 일반 BFS 문제였던 것이다,,,

 

 

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