알고리즘
[백준] 1012-유기농 배추 (Java)
주인 완
2024. 12. 23. 01:34
https://www.acmicpc.net/problem/1012
문제
구현 방식
육지(1)로 표시된 지점들을 탐색하면서 연결된 육지를 올바르게 판단하는 것이 관건인 문제이다.
방문하지 않은 칸을 방문할 때마다, 연결된 모든 칸을 한 번에 탐색하여 육지로 묶는 방식으로 문제를 접근하였다.
BFS를 위한 자료구조
- 2차원 배열 check로 방문 여부를 관리한다.
- 큐(Queue)를 활용하여 BFS를 구현한다.
- 이동 방향을 나타내기 위한 dy, dx 배열(상하좌우)을 준비한다.
로직
- 이중 for문을 통해 모든 좌표들을 하나씩 순회하면서 탐색한다.
- 아직 방문하지 않은 칸을 발견하면, 해당 칸에서 시작하는 새 육지를 찾은 것이므로, 육지 개수를 담당하는 변수의 값을 1 증가시킨다.
- 현재 좌표 (y, x)를 큐에 넣고, check[y][x] = 1로 방문 여부를 표시한다.
- 큐가 빌 때까지 다음 과정을 반복한다.
- 큐에서 현재 좌표 (y, x)를 꺼낸다.
- 상하좌우 방향으로 이동할 다음 좌표 (ny, nx)를 구한다.
- 오버플로우/언더플로우(배열 범위를 벗어남)와 육지 여부, 방문 여부(check[ny][nx])를 확인한다.
- 조건을 하나라도 충족하면 continue 구문을 통해 방문하지 않는다.
- 해당 조건들을 불충족 시, 방문하지 않은 육지이므로 check[ny][nx] = 1로 표시 후, 큐에 (ny, nx)를 삽입하여 해당 좌표 주변의 좌표들을 탐색하도록 한다.
BFS보다 DFS가 유리한 이유
최단 경로(거리 계산)가 필요하지 않으며, 단순히 연결된 좌표들만 파악하기에 DFS가 이론적으로 더 유리하다.
이유는 즉슨 DFS는 한 경로를 끝까지 파고드는 방식으로 진행되기 때문이다. 연결되어 있는 좌표를 '재귀 호출' 혹은 '스택'을 통해 계속 파고들기 때문에, 단순히 연결된 좌표들만 모두 방문해야 하는 상황에서는 코드가 비교적 간단해질 수 있다.
DFS 로직
- 방문 배열 초기화 : 새로운 테스트 케이스(처음 방문하는 육지)마다 check 배열 등을 초기화해주어야 한다.
- DFS 함수 호출 :
- 방문하지 않은 육지을 찾으면 dfs(y, x) 메서드를 호출한다.
- DFS 내부에서 상하좌우를 확인하며, 조건에 맞으면 dfs(y, x) 메서드를 재귀 호출한다.
정답(BFS)
import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static Queue<Point> queue = new LinkedList<>();
static int[] dy = {-1, 0, 1, 0};
static int[] dx = {0, 1, 0, -1};
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
boolean[][] arr = new boolean[m][n];
boolean[][] check = new boolean[m][n];
for (int j = 0; j < k; j++) {
st = new StringTokenizer(br.readLine());
int tmpY = Integer.parseInt(st.nextToken());
int tmpX = Integer.parseInt(st.nextToken());
arr[tmpY][tmpX] = true;
}
int cnt = 0;
int ny = 0, nx = 0, y = 0, x = 0;
for (int j = 0; j < m; j++) {
for (int l = 0; l < n; l++) {
if (arr[j][l]) {
if (!check[j][l]){
cnt++;
check[j][l] = true;
queue.offer(new Point(j, l));
}
}
while (!queue.isEmpty()) {
Point p = queue.poll();
y = p.x;
x = p.y;
for (int o = 0; o < 4; o++) {
ny = y + dy[i];
nx = x + dx[i];
if (ny < 0 || ny >= n || nx < 0 || nx >= m || !arr[ny][nx]) {
continue;
}
if (check[ny][nx]) {
continue;
}
check[ny][nx] = true;
queue.offer(new Point(ny, nx));
}
}
}
}
System.out.println(cnt);
}
}
}
정답(DFS)
import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[] dy = {-1, 0, 1, 0};
static int[] dx = {0, 1, 0, -1};
static boolean[][] arr, check;
static int ny, nx, y, x, cnt, m, n;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
arr = new boolean[m][n];
check = new boolean[m][n];
for (int j = 0; j < k; j++) {
st = new StringTokenizer(br.readLine());
int tmpY = Integer.parseInt(st.nextToken());
int tmpX = Integer.parseInt(st.nextToken());
arr[tmpY][tmpX] = true;
}
cnt = 0;
for (int j = 0; j < m; j++) {
for (int l = 0; l < n; l++) {
if (arr[j][l]) {
if (!check[j][l]){
cnt++;
dfs(j, l);
}
}
}
}
sb.append(cnt).append("\n");
}
System.out.println(sb);
}
private static void dfs(int j, int l) {
check[j][l] = true;
for (int i = 0; i < 4; i++) {
ny = j + dy[i];
nx = l + dx[i];
if (ny < 0 || ny >= m || nx < 0 || nx >= n) {
continue;
}
if (!check[ny][nx] && arr[ny][nx]) {
dfs(ny, nx);
}
}
}
}