mingssssss

1. 문제

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

2. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    
    // 전역 변수 설정
	static ArrayList<ArrayList<Integer>> list;
	static boolean[][] visited;
	static int[] dx = { -1, -1, -1, 0, 1, 1, 1, 0 };
	static int[] dy = { -1, 0, 1, 1, 1, 0, -1, -1 };
	static int answer = 0;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

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

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		list = new ArrayList<>();
		visited = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			list.add(new ArrayList<>());
		}

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				list.get(i).add(Integer.parseInt(st.nextToken()));
			}
		}
		// 입력 종료

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (visited[i][j] == false && list.get(i).get(j) == 1) {
					bfs(i, j, N, M, list, visited);
					answer++;
				}

			}
		}

		System.out.println(answer);

		// 출력
//		for (int i = 0; i < N; i++) {
//
//			for (int j = 0; j < M; j++) {
//				System.out.printf("%d ", list.get(i).get(j));
//			}
//			System.out.println();
//		}
	}

	private static void bfs(int r, int c, int N, int M, ArrayList<ArrayList<Integer>> list, boolean[][] visited) {

		Queue<int[]> q = new LinkedList<>();

		q.add(new int[] { r, c });
		visited[r][c] = true;

		while (!q.isEmpty()) {

			int[] now = q.poll();

			for (int i = 0; i < 8; i++) {

				int nextX = now[0] + dx[i];
				int nextY = now[1] + dy[i];

				if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
					continue;
				}

				if (visited[nextX][nextY] == true || list.get(nextX).get(nextY) != 1) {
					continue;
				}

				visited[nextX][nextY] = true;
				q.add(new int[] { nextX, nextY });

			}
		}

	}

}

3. 리뷰

전형적인 bfs 문제이다

상 하 좌 우 대각선까지 8방향 탐색을 통해 이어져 있는 1을 탐색하여

몇 개로 이루어져 있는지 확인하는 문제이다.

입력을 받아 ArrayList에 해당 값을 저장하고

전체 배열을 탐색하면서 방문하지 않았으면서 해당 좌푯값이 1이면 탐색을 시작했다.

8방향으로 탐색하면서 방문한 적이 없고, 다음 좌푯값이 1이라면

방문처리하고 Queue에 넣었다.

처음 bfs를 시작할 때는 어려웠는데 지금은 금방 풀 수 있어서 좋았다.