링크
https://www.acmicpc.net/problem/2667
문제 설명
(정답률 42.257%)
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
입력 예제
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
출력 예제
3
7
8
9
정답 코드
[-1, 0]
[0, -1] [0, 0] [0, 1]
[1, 0]위와 같이 방향을 나타내는 배열을 생성한다.
우선 모든 2차원 배열의 원소를 탐색해야 한다.
개 중에서 원소가 1일 때, 방문하지 않았을 때 dfs(또는 bfs) 메서드를 호출한다.
dfs의 경우 재귀를 호출하는 방식을 이용한다.
현재 좌표에서 각 방향을 탐색한 후
배열을 벗어나는 경우는 제외하고,
원소가 1일 때, 방문하지 않았을 때 재귀를 호출한다.
bfs의 경우 큐를 사용한다.
큐의 추가한 데이터의 좌표값을 얻어야 하기 때문에
int배열 타입으로 큐를 생성한다.
dfs와 다르게
현재 좌표에서 각 방향을 탐색한 다음
해당되는 모든 경우를 큐에 추가한 다음
큐에서 하나씩 좌표를 꺼내어 반복한다.
import java.util.*;
import java.io.*;
public class Main {
//[0, 1], [1, 0], [0, -1], [-1, 0]
//오른쪽, 아래, 왼쪽, 위
static final int[] dx = {0, 1, 0, -1};
static final int[] dy = {1, 0, -1, 0};
static boolean[][] visit;
static int[][] map;
static int N;
static int count;
static List<Integer> result = new ArrayList<>();
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
visit = new boolean[N][N];
//map 배열 입력값으로 할당
for (int i = 0; i < N; i++) {
int[] input = Arrays.stream(br.readLine().split(""))
.mapToInt(Integer::parseInt).toArray();
for (int j = 0; j < N; j++) {
map[i][j] = input[j];
}
}
//2차원 배열의 모든 경우 탐색
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
//집이 있는 곳인데 방문하지 않았을 때
if (map[i][j] == 1 && !visit[i][j]) {
count = 0; //카운트 초기화
dfs(i, j); //dfs 메서드 호출
//bfs(i, j); //bfs 메서드 호출
result.add(count);
}
}
}
Collections.sort(result);
System.out.println(result.size());
result.forEach(System.out::println);
}
//깊이 우선 탐색 메서드
private static void dfs(int x, int y) {
//방문으로 설정하고 카운트
visit[x][y] = true;
count++;
//상하좌우 탐색
for (int i = 0; i < 4; i++) {
//방향에 따라 좌표 갱신
int nextX = x + dx[i];
int nextY = y + dy[i];
//좌표가 배열 밖으로 벗어날 때
if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) {
continue;
}
//집이 있는 곳인데 방문하지 않았을 때
//재귀 호출
if (map[nextX][nextY] == 1 &&
!visit[nextX][nextY]) {
dfs(nextX, nextY);
}
}
}
//너비 우선 탐색
static void bfs(int x, int y) {
//int배열 타입으로 큐 생성
Queue<int[]> queue = new LinkedList<>();
//현재 좌표, 큐에 추가 및 방문 처리
queue.add(new int[]{x, y});
visit[x][y] = true;
//카운트
count++;
//큐가 빌 때까지 반복
while (!queue.isEmpty()) {
//큐의 첫번째 원소를 현재 좌표로 할당
int[] curPos = queue.poll();
int curX = curPos[0];
int curY = curPos[1];
//상하좌우 탐색
for (int i = 0; i < 4; i++) {
//방향에 따라 좌표 갱신
int nextX = curX + dx[i];
int nextY = curY + dy[i];
//좌표가 배열을 벗어날 때
if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) {
continue;
}
//집이 있는 곳인데 방문하지 않았을 때
if (map[nextX][nextY] == 1 && !visit[nextX][nextY]) {
//큐에 추가 및 방문 처리, 카운트
queue.add(new int[]{nextX, nextY});
visit[nextX][nextY] = true;
count++;
}
}
}
}
}정리
일부러 공부차원에서 dfs와 bfs을 이용한 방법 모두 사용하였다.
이전에 탐색 문제를 풀어봤기 때문에 응용하면 쉽게 풀 수 있을줄 알았는데
문제가 다르니 너무 어려웠다.
적응될 때 까지 탐색 문제만 풀어야겠다.
