Algorithm

[์•Œ๊ณ ๋ฆฌ์ฆ˜] DFS ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ ์•Œ์•„๋ณด๊ธฐ ( ๋ฐฑ์ค€ 2667๋ฒˆ ๋‹จ์ง€๋ฒˆํ˜ธ ๋ถ™์ด๊ธฐ with ์ž๋ฐ”)

์žฅ์šฉ์„ 2024. 2. 23. 20:38

 

๐Ÿค” DFS ( Depth First Search ) ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰?

 

๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ํ•˜๋‚˜์˜ ์ •์ ์œผ๋กœ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜์—ฌ ์ฐจ๋ก€๋Œ€๋กœ ๋ชจ๋“  ์ •์ ๋“ค์„ ํ•œ ๋ฒˆ์”ฉ ๋ฐฉ๋ฌธํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž…๋‹ˆ๋‹ค.

์ฆ‰ ๊ทธ๋ž˜ํ”„ ํ˜•ํƒœ์˜ ์ž๋ฃŒ๊ตฌ์กฐ์—์„œ ๋ฃจํŠธ ๋…ธ๋“œ์—์„œ ์‹œ์ž‘ํ•ด์„œ ๋‹ค์Œ ๋ถ„๊ธฐ๋กœ ๋„˜์–ด๊ฐ€๊ธฐ ์ „์— ํ•ด๋‹น ๋ถ„๊ธฐ๋ฅผ ์™„๋ฒฝํ•˜๊ฒŒ ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค.

๊ทธ๋ฆผ์ฒ˜๋Ÿผ ํ•œ ๋ฐฉํ–ฅ์œผ๋กœ ์ธ์ ‘ํ•œ ๋…ธ๋“œ๊ฐ€ ์—†์„ ๋•Œ๊นŒ์ง€ ํƒ์ƒ‰ํ•œ ํ›„ ์ด์ „ ๋…ธ๋“œ๋กœ ๋Œ์•„๊ฐ€์„œ ๋‹ค์Œ ์ธ์ ‘ํ•œ ๋…ธ๋“œ๋ฅผ ํƒ์ƒ‰ํ•˜๋ฉฐ ์ด ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•ฉ๋‹ˆ๋‹ค.

 

์žฅ์ 

  • ํ˜„์žฌ ๊ฒฝ๋กœ์ƒ์˜ ๋…ธ๋“œ๋ฅผ ๊ธฐ์–ตํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ ์€ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค.
  • ์ฐพ์œผ๋ ค๋Š” ๋…ธ๋“œ๊ฐ€ ๊นŠ์€ ๋‹จ๊ณ„์— ์žˆ๋Š” ๊ฒฝ์šฐ BFS๋ณด๋‹ค ๋น ๋ฅด๊ฒŒ ์ฐพ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋‹จ์ 

  • DFS๋ฅผ ํ†ตํ•ด ์–ป์–ด์ง„ ํ•ด๊ฐ€ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ผ๋Š” ๋ณด์žฅ์ด ์—†์Šต๋‹ˆ๋‹ค. DFS๋Š” ์ฐพ์œผ๋ ค๋Š” ํ•ด์— ๋„์ฐฉํ•˜๋ฉด ํƒ์ƒ‰์„ ์ข…๋ฃŒํ•˜๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.
  • ์ตœ์•…์˜ ๊ฒฝ์šฐ, ๊ฐ€๋Šฅํ•œ ๋ชจ๋“  ๊ฒฝ๋กœ๋ฅผ ํƒ์ƒ‰ํ•จ์œผ๋กœ ํ•ด์— ๋„๋‹ฌํ•˜๋Š” ๋ฐ ๊ฐ€์žฅ ์˜ค๋žœ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆด ์ˆ˜ ์žˆ๋‹ค.

 

โœ” ๋ฌธ์ œ ์œ ํ˜•

  • ๊ฒฝ๋กœํƒ์ƒ‰ ์œ ํ˜• ( ์ตœ๋‹จ๊ฑฐ๋ฆฌ, ์‹œ๊ฐ„ )
  • ๋„คํŠธ์›Œํฌ ์œ ํ˜• ( ์—ฐ๊ฒฐ )
  • ์กฐํ•ฉ ์œ ํ˜• (๋ชจ๋“  ์กฐํ•ฉ ๋งŒ๋“ค๊ธฐ )

 

โœ” ์‹œ๊ฐ„ ๋ณต์žก๋„

DFS๋ฅผ ์‚ฌ์šฉํ•  ๋•Œ ๊ทธ๋ž˜ํ”„๋ฅผ ์ธ์ ‘ ํ–‰๋ ฌ ๋˜๋Š” ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ ๋กœ ํ‘œํ˜„ํ•  ๊ฒฝ์šฐ์— ๋‹ฌ๋ผ์ง‘๋‹ˆ๋‹ค.

์ถœ์ฒ˜ : https://howtolivelikehuman.tistory.com/75

 

์ธ์ ‘ ํ–‰๋ ฌ์€ ์ด์ฐจ์› ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๊ทธ๋ž˜ํ”„์˜ Vertex์˜ ์ˆ˜ ๋งŒํผ ์ด์ฐจ์› ๋ฐฐ์—ด์„ ์ƒ์„ฑํ•ฉ๋‹ˆ๋‹ค.

DFS์˜ ํŠน์„ฑ์ƒ ํ•ด๊ฐ€ ์ •ํ•ด์ ธ์žˆ์ง€ ์•Š์œผ๋ฉด ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ํƒ์ƒ‰ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

์ด์ฐจ์› ๋ฐฐ์—ด์˜ ๋ชจ๋“  ๋ฐฉ์„ ํƒ์ƒ‰ํ•œ๋‹ค๋ฉด Vertex * Vertex ์ฆ‰, O( N^2)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€๊ฒŒ ๋ฉ๋‹ˆ๋‹ค

 

์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋Š” LinkedList๋ฅผ ์‚ฌ์šฉํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๊ฐ Vertex(๋…ธ๋“œ)์—์„œ ์—ฐ๊ฒฐ์„ (Edge)์œผ๋กœ ์—ฐ๊ฒฐ๋œ Vertex๊นŒ์ง€ ํƒ์ƒ‰ํ•˜๋ฉฐ ๊ฐ Vertex์™€ Edge์˜ ์ˆ˜๋งŒํผ ํƒ์ƒ‰ํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ์ฆ‰, Vertex + Edge๋ฅผ ๋”ํ•œ ๋งŒํผ O( Vertex + Edge )์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

 

โœ” ํƒ์ƒ‰ ๋ฐฉ๋ฒ•

ํƒ์ƒ‰์€ Stack ๋˜๋Š” ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋ฐฑ์ค€ 2667๋ฒˆ์„ ์˜ˆ์ œ๋กœ DFS๋ฅผ ์‚ฌ์šฉํ•ด ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

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

 

2667๋ฒˆ: ๋‹จ์ง€๋ฒˆํ˜ธ๋ถ™์ด๊ธฐ

<๊ทธ๋ฆผ 1>๊ณผ ๊ฐ™์ด ์ •์‚ฌ๊ฐํ˜• ๋ชจ์–‘์˜ ์ง€๋„๊ฐ€ ์žˆ๋‹ค. 1์€ ์ง‘์ด ์žˆ๋Š” ๊ณณ์„, 0์€ ์ง‘์ด ์—†๋Š” ๊ณณ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค. ์ฒ ์ˆ˜๋Š” ์ด ์ง€๋„๋ฅผ ๊ฐ€์ง€๊ณ  ์—ฐ๊ฒฐ๋œ ์ง‘์˜ ๋ชจ์ž„์ธ ๋‹จ์ง€๋ฅผ ์ •์˜ํ•˜๊ณ , ๋‹จ์ง€์— ๋ฒˆํ˜ธ๋ฅผ ๋ถ™์ด๋ ค ํ•œ๋‹ค. ์—ฌ

www.acmicpc.net

๋ฐฑ์ค€ 2667 ๋ฌธ์ œ

 

๊ทธ๋ฆผ์ฒ˜๋Ÿผ ํ–‰๋ ฌ์—์„œ ์ธ์ ‘ํ•œ ์ง‘( 1 )์˜ ์ˆ˜์™€ ๊ฐ ์ง‘์ด ๋ชจ์—ฌ์žˆ๋Š” ๋‹จ์ง€์˜ ์ˆ˜๋ฅผ ์ฐพ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

๐Ÿ”Ž ์žฌ๊ท€ํ•จ์ˆ˜ ์‚ฌ์šฉ

์กฐ๊ฑด์— ๋งž๋Š” ์ธ์ ‘ํ•œ ๋…ธ๋“œ๋ฅผ ๋‹ค์‹œ ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•˜์—ฌ ํƒ์ƒ‰ํ•ฉ๋‹ˆ๋‹ค.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.StringBuilder;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class Main{

	static List<Integer> result;
    static boolean[][] chk;
    static int[][] map;
    static int cnt, n;
    
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
        
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        chk = new boolean[n][n];
        result = new ArrayList<>();
        cnt = 1;

		// ์ž…๋ ฅ๋ฐ›์€ ์ง€๋„(ํ–‰์—ด)๋ฅผ ํƒ์ƒ‰ํ•˜๊ธฐ์œ„ํ•ด ์ด์ฐจ์›๋ฐฐ์—ด์— ์ถ”๊ฐ€ํ•ด์ค๋‹ˆ๋‹ค.
        for( int i = 0; i<n; i++){
            String[] arr = br.readLine().split("");
            for( int j = 0; j<n; j++){
                map[i][j] = Integer.parseInt(arr[j]);
            }
        }

        for( int i = 0; i<n; i++){
            for( int j = 0; j<n; j++){
                if( map[i][j] == 1 && !chk[i][j] ){ // 1์ด๊ณ  ์ฒดํฌํ•˜์ง€ ์•Š์€ ์ฆ‰, ํƒ์ƒ‰ํ•˜์ง€ ์•Š์€ ์ง‘
                    dfs(i, j); // dfs ํ˜ธ์ถœ
                    result.add(cnt); // dfs๋ฅผ ํ†ตํ•ด ์ธ์ ‘ํ•œ ์ง‘ ์ˆ˜ ์ถ”๊ฐ€
                    cnt = 1; // cnt ์ดˆ๊ธฐํ™”
                }
            }
        }    
        
        Collections.sort(result); // ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ
        sb.append(result.size()).append("\n");
        for( int i : result ){
            sb.append(i).append("\n");
        }
        
        System.out.print(sb);
	}
    
    static void dfs(int y, int x){
        chk[y][x] = true;
        int[] dy = {0,1,0,-1};
        int[] dx = {1,0,-1,0};
        for( int i = 0; i<4; i++){ // 4๋ฐฉํ–ฅ์˜ ๋…ธ๋“œ๋ฅผ ๋ชจ๋‘ ํƒ์ƒ‰
            int ny = y + dy[i];
            int nx = x + dx[i];
            if( ny >= 0 && nx >= 0 && ny < n && nx < n ){ //์ธ์ ‘ํ•œ ๋…ธ๋“œ๊ฐ€ ์—†๋‹ค๋ฉด ํƒ์ƒ‰ํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
                if( map[ny][nx] == 1 && chk[ny][nx] == false){
                    cnt++;
                    dfs(ny, nx); // dfs์žฌ๊ท€ ํ˜ธ์ถœ
                }
            }
        }
    }
    
}

 

๐Ÿ”Ž Stack ์‚ฌ์šฉ

 ์กฐ๊ฑด์— ๋งž๋Š” ์ธ์ ‘ํ•œ ๋…ธ๋“œ๋“ค์„ stack์— ๋ชจ๋‘ ๋‹ด๊ณ  ํ•˜๋‚˜์”ฉ ์ œ๊ฑฐํ•˜๋ฉด์„œ ํƒ์ƒ‰์„ ์ˆ˜ํ–‰ํ•ฉ๋‹ˆ๋‹ค.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.StringBuilder;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

public class Main{

	static List<Integer> result;
    static boolean[][] chk;
    static int[][] map;
    static int cnt, n;
    static Stack<int[]> stack;
    
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
        
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        chk = new boolean[n][n];
        result = new ArrayList<>();
        stack = new Stack<>();
        cnt = 1;

		// ์ž…๋ ฅ๋ฐ›์€ ์ง€๋„(ํ–‰์—ด)๋ฅผ ํƒ์ƒ‰ํ•˜๊ธฐ์œ„ํ•ด ์ด์ฐจ์›๋ฐฐ์—ด์— ์ถ”๊ฐ€ํ•ด์ค๋‹ˆ๋‹ค.
        for( int i = 0; i<n; i++){
            String[] arr = br.readLine().split("");
            for( int j = 0; j<n; j++){
                map[i][j] = Integer.parseInt(arr[j]);
            }
        }

        for( int i = 0; i<n; i++){
            for( int j = 0; j<n; j++){
                if( map[i][j] == 1 && !chk[i][j]){
                    dfsUseStack(i, j);
                    result.add(cnt);
                    cnt=1;
                }
            }
        }   
        
        Collections.sort(result); // ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ
        sb.append(result.size()).append("\n");
        for( int i : result ){
            sb.append(i).append("\n");
        }
        
        System.out.print(sb);
	}
    
    static void dfsUseStack(int y, int x){
        chk[y][x] = true;
        stack.push(new int[]{y, x});
        int[] dy = {0,1,0,-1};
        int[] dx = {1,0,-1,0};

        while (!stack.isEmpty()){
            int[] arr = stack.pop();
            for( int i = 0; i<4; i++){
                int ny = arr[0] + dy[i];
                int nx = arr[1] + dx[i];
                if( ny >= 0 && nx >= 0 && ny < n && nx < n ){ //ํ•˜์ง€๋งŒ ์˜† ๋…ธ๋“œ๊ฐ€ ์—†๋‹ค๋ฉด ํƒ์ƒ‰ํ•˜์ง€ ์•Š๋„๋ก ์กฐ๊ฑด
                    if( map[ny][nx] == 1 && chk[ny][nx] == false){
                        cnt++;
                        chk[ny][nx] = true;
                        stack.push(new int[]{ny, nx}); //์กฐ๊ฑด์— ๋งž๋Š” ์ธ์ ‘๋…ธ๋“œ๋ฅผ stack์— ์ถ”๊ฐ€ํ•ฉ๋‹ˆ๋‹ค.
                    }
                }
            }
        }

    }
    
}

 


 

๐Ÿ“š Reference :

https://howtolivelikehuman.tistory.com/75

https://velog.io/@sukong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90-%EA%B9%8A%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89DFS