DFS를 Stack을 이용해서 풀어보자.

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

2667번: 단지번호붙이기

 

재귀함수를 이용하는게 아닌  Stack구조를 이용하여서 문제를 풀어보았다.

기존 DFS 탐색은 Stack 많은 값이 쌓이면 스택오버플로우를 일으킨다. 하지만 Stack을 사용하여 DFS를 구현하면 적은 메모리로 깊이 우선탐색을 구현할수가 있다.

 

일단 Stack은 두가지를 이용한다. 첫번째는 Stack은 i j 좌표값을 저장한다. 두번째는 Stackd 는 어느방향까지 탐색했었는지를 저장한다.

 

package com.ssafy.algo;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class 두더지굴 {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
 
        int Map[][] = new int[N][N];
        boolean check[][] = new boolean[N][N];
        int Stack[] = new int[N * N];
        int Stackd[] = new int[N * N];
        int sSize = -1;
 
        for (int i = 0; i < N; i++) {
            char[] c = br.readLine().toCharArray();
            for (int j = 0; j < N; j++) {
                Map[i][j] = c[j] - '0';
            }
        }
 
        ArrayList<Integer> cnt = new ArrayList<>();
        int thisCnt = 0;
        int dy[] = { 0, 0, -1, 1 };
        int dx[] = { 1, -1, 0, 0 };
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (Map[i][j] == 1 && check[i][j] == false) {
                    thisCnt = 0;
                    Stack[++sSize] = i * N + j;
                    Stackd[sSize] = 0;
                    while (sSize >= 0) {
                        int y = Stack[sSize] / N;
                        int x = Stack[sSize] % N;
                        if (!check[y][x]) {
                            thisCnt++;
                            check[y][x] = true;
                        }
 
                        boolean thisCheck = true;
                        for (int d = Stackd[sSize]; d < 4; d++) {
                            int ny = y + dy[d];
                            int nx = x + dx[d];
 
                            if (ny < 0 || nx < 0 || ny >= N || nx >= N)
                                continue;
                            if (Map[ny][nx] == 0)
                                continue;
                            if (check[ny][nx])
                                continue;
                            Stackd[sSize] = d+1;
                            Stack[++sSize] = ny * N + nx;
                            Stackd[sSize] = 0;
                            
                            thisCheck = false;
                            break;
                        }
                        if (thisCheck) {
                            --sSize;
                        }
 
                    }
                    cnt.add(thisCnt);
 
                }
 
            }
        }
 
        System.out.println(cnt.size());
        Collections.sort(cnt);
        for (int i = 0; i < cnt.size(); i++) {
            System.out.println(cnt.get(i));
        }
 
    }
 
}