구현 with BFS

백준 11559번 구현 문제를 BFS로 Java를 이용해 풀어보았다. 처음에 DFS로 푸는 개뻘짓을 하다가 나중에서야 ㅗ 모양은 DFS로 탐색할 수 없음을 디버깅하며 깨닫고 BFS로 선회해서 풀었다...

DFS와 BFS에 대한 기본적인 이해조차 제대로 되어 있지 않음을 다시금 확인할 수 있었다. 슬펐다... ㅆ..

---

BFS를 이용하자

같은 색깔끼리 연결되어 있는 것들을 끝까지 찾아갈 때 ㅗ와 같은 모양도 탐색하기 위해서는 DFS가 아닌 BFS를 이용해야 한다. 말 그대로 깊이 우선이 아닌 너비 우선으로 가야하기 때문이다. 이 간단하고 명료한 것을... 아직 갈 길이 멀다. ㅆ..ㅑ...ㅇ...

그리고 4개 이상 모인 그룹들을 구분해주기 위한 장치들이 몇 가지 필요하다. 한 텀에 터뜨릴 모든 좌표들을 담은 List를 만들어주고, 4개 이상 그룹인지 아닌지에 따라 터뜨릴 List에 추가해줄지 그리고 터뜨린 후에 밑으로 떨어뜨려줄 메소드까지 세 가지가 필요하다.

터뜨릴 List에 추가까지 담당하는 bfs 메소드의 코드는 다음과 같다.

static void bfs(int row, int col){
        if(visited[row][col])   return; // 이미 방문한 지점이면 넘겨
        if(map[row][col]=='.')  return; // 빈 칸이면 넘겨
        visited[row][col] = true;

        Queue<int[]> q = new LinkedList<>();
        int chained_num = 1;
        q.add(new int[]{row,col});
        chainedPos.add(new int[]{row,col});
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                int[] cur = q.poll();
                for(int dir=0; dir<4; dir++){
                    int n_row = cur[0] + move[dir][0]; int n_col = cur[1] + move[dir][1];
                    if(n_row<0 || n_row>11 || n_col<0 || n_col>5)   continue;
                    if(visited[n_row][n_col])   continue;
                    if(map[row][col]!=map[n_row][n_col])    continue;
                    q.add(new int[]{n_row,n_col});
                    visited[n_row][n_col] = true;
                    chainedPos.add(new int[]{n_row,n_col});
                    chained_num++;
                }
            }
        }
        if(chained_num<4)   chainedPos.clear(); // 4개 못 채웠으면 지워버리고
        willBeDestroyed.addAll(chainedPos); // 4개 이상이면 실제로 터뜨릴 리스트에 추가해주자
    }

---

빈 곳으로 떨어뜨릴 fallDown()

우선 터뜨릴 List를 순회하며 터뜨려주고, 그 후에 빈 칸 채워 넣으며 떨궈주면 된다.

떨궈주는 작업은 각 col마다 밑에서 위로 올라가며 Queue에 색깔들을 집어 넣은 후에, 밑에서부터 poll()하며 차곡차곡 채워 넣어주면 된다.

static void fallDown(){
        for(int[] pos: willBeDestroyed){ // 터뜨릴 목록 다 터뜨려서 빈 칸으로 만들어주자
            map[pos[0]][pos[1]] = '.';
        }
        willBeDestroyed.clear();

        Queue<Character> q = new LinkedList<>();
        for(int col=0; col<6; col++){ // 떨구는 건 col 별로 확인해주자
            for(int row=11; row>=0; row--){ // 아래서부터 위로 올라가며 색깔들 모아주고 다 모으면 맨 아래서부터 채워주자
                if(map[row][col]=='.')  continue; // 빈 칸이면 넘기고
                q.add(map[row][col]);
                map[row][col] = '.';
            }
            if(q.isEmpty()) continue;
            int size = q.size();
            for(int i=0; i<size; i++)
                map[11-i][col] = q.poll();
        }
    }

---

아래는 내가 제출한 코드다.

import java.util.LinkedList;
import java.util.Queue;
import java.io.*;

public class boj11559 {
    static char[][] map = new char[12][6];
    static boolean[][] visited;
    static int chainOccurence = 0;
    static int[][] move = { {-1,0}, {1,0}, {0,-1}, {0,1} };// 상하좌우
    static LinkedList<int[]> chainedPos = new LinkedList<>(), willBeDestroyed = new LinkedList<>();

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=0; i<12; i++){
            String input = bfr.readLine();
            for(int j=0; j<6; j++){
                map[i][j] = input.charAt(j);
            }
        }

        while(true){
            visited = new boolean[12][6];
            for(int i=0; i<12; i++)
                for(int j=0; j<6; j++)
                    bfs(i,j);
            if(willBeDestroyed.isEmpty())   break;
            else    chainOccurence++;
            fallDown();
        }

        bfw.write(String.valueOf(chainOccurence));
        bfw.close();
    }

    static void bfs(int row, int col){
        if(visited[row][col])   return; // 이미 방문한 지점이면 넘겨
        if(map[row][col]=='.')  return; // 빈 칸이면 넘겨
        visited[row][col] = true;

        Queue<int[]> q = new LinkedList<>();
        int chained_num = 1;
        q.add(new int[]{row,col});
        chainedPos.add(new int[]{row,col});
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                int[] cur = q.poll();
                for(int dir=0; dir<4; dir++){
                    int n_row = cur[0] + move[dir][0]; int n_col = cur[1] + move[dir][1];
                    if(n_row<0 || n_row>11 || n_col<0 || n_col>5)   continue;
                    if(visited[n_row][n_col])   continue;
                    if(map[row][col]!=map[n_row][n_col])    continue;
                    q.add(new int[]{n_row,n_col});
                    visited[n_row][n_col] = true;
                    chainedPos.add(new int[]{n_row,n_col});
                    chained_num++;
                }
            }
        }
        if(chained_num<4)   chainedPos.clear(); // 4개 못 채웠으면 지워버리고
        willBeDestroyed.addAll(chainedPos); // 4개 이상이면 실제로 터뜨릴 리스트에 추가해주자
    }

    static void fallDown(){
        for(int[] pos: willBeDestroyed){ // 터뜨릴 목록 다 터뜨려서 빈 칸으로 만들어주자
            map[pos[0]][pos[1]] = '.';
        }
        willBeDestroyed.clear();

        Queue<Character> q = new LinkedList<>();
        for(int col=0; col<6; col++){ // 떨구는 건 col 별로 확인해주자
            for(int row=11; row>=0; row--){ // 아래서부터 위로 올라가며 색깔들 모아주고 다 모으면 맨 아래서부터 채워주자
                if(map[row][col]=='.')  continue; // 빈 칸이면 넘기고
                q.add(map[row][col]);
                map[row][col] = '.';
            }
            if(q.isEmpty()) continue;
            int size = q.size();
            for(int i=0; i<size; i++)
                map[11-i][col] = q.poll();
        }
    }
}

오늘 배운 것

나는 DFS와 BFS도 구분할 줄 모르는 놈이다.
너비 우선인지 깊이 우선인지 구분하고 들어가자. 멍청아