Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

24. DFS와 BFS

그래프를 순회하는 알고리즘을 배워 봅시다.

Java / Python

3. 단지번호붙이기

2667번

2차원 배열을 그래프로 표현해 BFS나 DFS로 순회하는 문제

이번 문제는 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하는 문제입니다.

• 입력
  
  첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
  
  
• 출력
  
  첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

DFS(Depth-First Search) : 깊이 우선 탐색

• 재귀나 스택으로 구현
• 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

BFS(Breath-First Search) : 너비 우선 탐색

• 큐로 구현 (FIFO원칙으로 탐색)
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

• Java

import java.io.*;
import java.util.*;

public class Main {
	static int[] dx = {-1, 1, 0, 0};	// 상하좌우	
	static int[] dy = {0, 0, -1, 1};	// 상하좌우
	static int N, cnt;	// 지도의 크기, 집 숫자
	static int[][] Map;	// 지도
	static boolean[][] check;	// 방문 여부
	static ArrayList<Integer> result = new ArrayList();
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
              
		N = Integer.parseInt(br.readLine());	
      
		Map = new int[N][N];      
		check = new boolean[N][N];
        
		// 지도 입력 받기
		for(int i = 0; i < N; i++){
			String str = br.readLine();
			for(int j = 0; j < N; j++){
				Map[i][j] = str.charAt(j) - '0';
			}
		}
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				if(Map[i][j] == 1 && !check[i][j]){
					cnt = 1;
					bfs(i,j);
					result.add(cnt);
				}
			}
		}
        
		Collections.sort(result);
        
		bw.write(result.size() + "\n");
        
		for(int i = 0; i < result.size(); i++)
			bw.write(result.get(i) + "\n");
        
		bw.flush();
		bw.close();
		br.close();
	}

	public static int bfs(int x, int y) {
		check[x][y] = true;
        
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
            
			if (nx >= 0 && ny >= 0 && nx < N && ny < N){
				if(Map[nx][ny] == 1 && !check[nx][ny]){
					bfs(nx, ny);
					cnt++;
				}
			}
		}
		return cnt;
    }
}

• Python

import sys
N = int(sys.stdin.readline())
graph = [list(sys.stdin.readline()) for _ in range(N)]
cnt = 0
apt = []
              
def dfs(x, y):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    global cnt
    graph[x][y] = '0'
    cnt += 1 
    for i in range(4):
        nx = x + dx[i] 
        ny = y + dy[i]
        if N > nx >= 0 and N> ny >= 0 and graph[nx][ny] == '1':
            dfs(nx,ny)


for i in range(N):
    for j in range(N):
        if graph[i][j] == '1':
            cnt = 0
            dfs(i, j)
            apt.append(cnt)
    
print(len(apt))
apt.sort()
for i in apt:
    print(i)