mingssssss

1. 문제

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

2. 코드

package mymain;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class BOJ_2667 {

	static ArrayList<ArrayList<Integer>> list;
	static boolean[][] visited;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static int N;
	static int cnt;
	static int r;
	static int c;

	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());

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

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

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

		for (int i = 0; i < N; i++) {
			String s = br.readLine();
			for (int j = 0; j < N; j++) {
				list.get(i).add(s.charAt(j) - '0');
			}
		}
		// 입력 종료

		int total = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {

				if (visited[i][j] == false && list.get(i).get(j) == 1) {
					dfs(i, j);
					total++;
					answer.add(cnt);
					cnt = 0;
				}
			}
		}
		
		Collections.sort(answer);
		answer.add(0, total);
		for (int i = 0; i < answer.size(); i++) {
			System.out.println(answer.get(i));
		}

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

	}

	private static void dfs(int r, int c) {

		visited[r][c] = true;
		cnt++;

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

			int nextX = r + dx[i];
			int nextY = c + dy[i];

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

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

			visited[nextX][nextY] = true;
			dfs(nextX, nextY);
		}
	}

}

3. 리뷰

전형적인 탐색 문제이다.

몇 가지의 영역으로 나누어져 있는 부분의 개수와, 각 영역의 크기를 구하는 문제이다.

bfs가 아닌 dfs로 푸는 연습을 하기 위해 선택했다.

먼저 2차원 ArrayList를 생성한 후 입력을 받는다.

이중 for문으로 탐색하면서 방문한 곳이 아니면서 해당 좌푯값이 1이면 탐색을 시작한다.

또한 dfs가 한 번 돌면 영역 체크가 끝났으므로, 영역의 수를 카운트 해준다.

또한 dfs가 끝났다면 카운트 수를 초기화 해준다.

오름차순으로 정렬하라 했으므로, ArrayList를 하나 더 생성해서

각 영역의 크기를 집어넣고, sort를 해준다.

그리고 맨 앞에 영역의 수를 집어넣어준다.

dfs 역시 탐색 기반이라 bfs와 구현은 다를 것이 없는 것 같다.

각 조건을 어떻게 체크하는지를 잘 살펴봐야겠다.