반응형
문제
https://www.acmicpc.net/problem/2667
해설
DFS와 BFS 모두 사용하여 풀이가 가능한 문제라고 한다. 두 방법 모두 이용하여 풀어보았다. 아직 실력이 초보에 가까워 직관적으로 구현하려고 노력하였다.
이 문제는 DFS가 더 적절한 방법이라고 생각한다. 이 문제에선 DFS의 탐색 속도가 조금 더 빠르기 때문이다.
BFS는 주변의 요소만 판단하며 거의 마지막 그리드까지 하나씩 확인해나가야 한다. 반면, DFS는 하나의 hit를 찾았을 때 한 번에 끝까지 모든 인접 경로를 탐색하는 방식이므로 visited 검사를 통해 BFS보다 좀 더 빠르게 조건문에서 필터가 가능하다. 다만 DFS를 사용하였을 땐 Stack Overflow의 위험이 내재되어 있다는 점은 인지하여야 한다.
Python
DFS
from sys import stdin
def dfs(row: int, col: int):
global house_count
visited[row][col] = True
house_count += 1
if 0 < row and not visited[row-1][col] and arr[row-1][col]: # up
dfs(row-1, col)
if row < n-1 and not visited[row+1][col] and arr[row+1][col]: # down
dfs(row+1, col)
if 0 < col and not visited[row][col-1] and arr[row][col-1]: # left
dfs(row, col-1)
if col < n-1 and not visited[row][col+1] and arr[row][col+1]: # right
dfs(row, col+1)
n = int(stdin.readline())
arr = [list(map(int, list(stdin.readline().strip()))) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
result = []
for i in range(n):
for j in range(n):
if not visited[i][j] and arr[i][j] == 1:
house_count = 0
dfs(i, j)
result.append(house_count)
print(len(result))
[print(v) for v in sorted(result)]
BFS
from sys import stdin
from collections import deque
def bfs(row: int, col: int):
queue = deque()
queue.append([row, col])
visited[row][col] = True
house_count = 1
while queue:
row, col = queue.popleft()
if 0 < row and not visited[row-1][col] and arr[row-1][col]: # up
house_count += 1
visited[row-1][col] = True
queue.append((row-1, col))
if row < n-1 and not visited[row+1][col] and arr[row+1][col]: # down
house_count += 1
visited[row+1][col] = True
queue.append((row+1, col))
if 0 < col and not visited[row][col-1] and arr[row][col-1]: # left
house_count += 1
visited[row][col-1] = True
queue.append((row, col-1))
if col < n-1 and not visited[row][col+1] and arr[row][col+1]: # right
house_count += 1
visited[row][col+1] = True
queue.append((row, col+1))
return house_count
n = int(stdin.readline())
arr = [list(map(int, list(stdin.readline().strip()))) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
result = []
for i in range(n):
for j in range(n):
if not visited[i][j] and arr[i][j]:
result.append(bfs(i, j))
print(len(result))
[print(v) for v in sorted(result)]
Java
DFS
import java.io.*;
import java.util.*;
public class Main {
static int house_count;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
int[][] arr = new int[n][n];
int[][] visited = new int[n][n];
for(int i=0; i<n; i++){
String row = br.readLine();
for(int j=0; j<row.length(); j++){
arr[i][j] = Integer.parseInt(row.substring(j, j+1));
visited[i][j] = 0;
}
}
List<Integer> result = new ArrayList<>();
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(visited[i][j]==0 && arr[i][j]==1){
house_count = 0;
dfs(arr, visited, n, i, j);
result.add(house_count);
}
}
}
Collections.sort(result);
sb.append(result.size()).append("\n");
for(int v : result){
sb.append(v).append("\n");
}
System.out.println(sb);
}
public static void dfs(int[][] arr, int[][] visited, int n, int row, int col) {
visited[row][col] = 1;
house_count += 1;
if(0<row && visited[row-1][col]==0 && arr[row-1][col]==1){ // up
dfs(arr, visited, n, row-1, col);
}
if(row<n-1 && visited[row+1][col]==0 && arr[row+1][col]==1){ // down
dfs(arr, visited, n, row+1, col);
}
if(0<col && visited[row][col-1]==0 && arr[row][col-1]==1){ // left
dfs(arr, visited, n, row, col-1);
}
if(col<n-1 && visited[row][col+1]==0 && arr[row][col+1]==1){ // right
dfs(arr, visited, n, row, col+1);
}
}
}
BFS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
int[][] arr = new int[n][n];
int[][] visited = new int[n][n];
for(int i=0; i<n; i++){
String row = br.readLine();
for(int j=0; j<row.length(); j++){
arr[i][j] = Integer.parseInt(row.substring(j, j+1));
visited[i][j] = 0;
}
}
List<Integer> result = new ArrayList<>();
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(visited[i][j]==0 && arr[i][j]==1){
result.add(bfs(arr, visited, n, i, j));
}
}
}
Collections.sort(result);
sb.append(result.size()).append("\n");
for(int v : result){
sb.append(v).append("\n");
}
System.out.println(sb);
}
public static int bfs(int[][] arr, int[][] visited, int n, int row, int col) {
Queue<List<Integer>> queue = new LinkedList<>();
queue.add(Arrays.asList(row, col));
visited[row][col] = 1;
int house_count = 1;
while(!queue.isEmpty()){
List<Integer> coord = queue.poll();
row = coord.get(0);
col = coord.get(1);
if(0<row && visited[row-1][col]==0 && arr[row-1][col]==1){ // up
house_count++;
visited[row-1][col] = 1;
queue.add(Arrays.asList(row-1, col));
}
if(row<n-1 && visited[row+1][col]==0 && arr[row+1][col]==1){ // down
house_count++;
visited[row+1][col] = 1;
queue.add(Arrays.asList(row+1, col));
}
if(0<col && visited[row][col-1]==0 && arr[row][col-1]==1){ // left
house_count++;
visited[row][col-1] = 1;
queue.add(Arrays.asList(row, col-1));
}
if(col<n-1 && visited[row][col+1]==0 && arr[row][col+1]==1){ // right
house_count++;
visited[row][col+1] = 1;
queue.add(Arrays.asList(row, col+1));
}
}
return house_count;
}
}
반응형
