⭐ 문제

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

난이도

🧐 시도

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
static int N, M;
static int[][] map;
static int ans;

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

static class Node {
    int y; int x;

    Node (int y, int x){
        this.y = y; this.x = x;
    }
}
static boolean[][] visited;
public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int T = Integer.parseInt(br.readLine());

    for(int t=0; t<T; ++t) {
        ans = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N+1][M+1];
        visited = new boolean[N+1][M+1];

        for(int i=0; i<N; ++i) {
            String line = br.readLine();

            for(int j=0; j<M; ++j) {
                if(line.charAt(j) == '#') {
                    map[i][j] = 1; // 양
                } else {
                    map[i][j] = 0;
                }
            }
        }

        for(int i=0; i<N; ++i) {
            for(int j=0; j<M; ++j) {
                if(map[i][j] == 0) continue;
                if(visited[i][j]) continue;
                bfs(i, j);
                ans++;
            }
        }

        bw.write(ans + "\n");

    }

    bw.flush();

}

static void bfs(int y, int x) {
    Queue<Node> q = new LinkedList<>();

    visited[y][x] = true;
    q.add(new Node(y, x));

    while(!q.isEmpty()) {
        int cy = q.peek().y, cx = q.peek().x;
        q.remove();

        for(int i=0; i<4; ++i) {
            int ny = cy+dy[i], nx = cx+dx[i];

            if(ny > N || ny < 0 || nx > M || nx < 0) continue;
            if(map[ny][nx] == 0) continue;
            if(visited[ny][nx]) continue;

            visited[ny][nx] = true;
            q.add(new Node(ny, nx));
        }

    }
}

}

📝 풀이

풀이
격자에서 그래프 탐색을 돌리는 가장 기본적인 그래프 이론 유형이다.
이전에 풀었던 [음식물 피하기], [섬의 개수]와 거의 입력 포맷만 다르고 풀이가 거의 같은 문제이다.

나는 BFS로 풀었지만, DFS도 가능하다.

다음의 자료구조를 선언해주었다.
static int[][] map; // 양(#)인 칸은 1, 풀(.)인 칸은 0을 저장해준다.
static boolean[][] visited;

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

map = new int[N+1][M+1];
visited = new boolean[N+1][M+1];
map: 양(#)인 칸은 1, 풀(.)인 칸은 0을 저장해준다.
visited: bfs로 이미 방문한 곳에 true를 저장한다. 처음엔 모두 false로 초기화 되어 있다.
dy, dx: bfs를 돌 때 인접한 칸을 쉽게 순회할 수 있도록 만들었다.
한줄씩 입력을 받으면서 #이면 map에 1, .이면 map에 0을 입력해줬다. 입력 사이사이에 공백이 없으므로 줄 단위로 입력을 받아서 문자(char)를 돌아야한다는 점이 주의할 점인 것 같다.
for(int i=0; i<N; ++i) {
String line = br.readLine();

 for(int j=0; j<M; ++j) {
 	if(line.charAt(j) == '#') {
     	map[i][j] = 1; // 양
 	} else {
     	map[i][j] = 0;
 	}

}
}
map 전체 칸을 이중포문으로 돌면서 각 칸에서 bfs를 실행한다. 단 visited[i][j] 값이 true이면 실행하지 않는다. (이미 앞서 다른 무리에 포함되어 방문된 곳이기 때문이다.)
예를 들면 아래 그림 예시에서, bfs(1, 3)을 실행하면, (1,3) 뿐만 아니라 (2, 2), (2, 3), (3, 3)도 bfs를 통해 다 방문해서 visited의 값이 true가 된다. 이 격자들은 이미 무리에 속해서 방문된 곳이므로 bfs를 돌리지 않고 넘어가는 것이다.
for(int i=0; i<N; ++i) {
for(int j=0; j<M; ++j) {
if(map[i][j] == 0) continue;
if(visited[i][j]) continue;
bfs(i, j);
ans++;
}
}
bfs가 시행된 횟수가 양 무리의 수가 된다. 이 문제는 T를 입력 받아서 여러 테스트 코드에 대해서 실행하므로, 각각의 테스트 케이스마다 visited 배열을 다시 할당해주거나(모든 값이 false가 되도록), 초기화를 해주어야한다는 점을 주의해야할 것 같다.

❓ 느낌점

지피티 도움없이는 풀수가 없다