Java | 백준 1388 바닥 장식 문제풀이 및 분석

백준 1388 바닥 장식 문제에 대한 글입니다.

백준 1388 바닥 장식

백준 1388 바닥장식

문제

문제 내용은 아래 링크에서 확인할 수 있다.

1388번: 바닥 장식

분석

DFS로 풀 수 있는 문제이다. 특징은 한 기점에서 고려해야 할 다음 방향이 하나이므로 단순한 DFS이다.

풀이

재귀 호출을 이용한 DFS

execute() 메서드를 이용해서 문제 해결을 시작한다. map의 모든 요소를 순차적으로 방문하며 탐색한다.

(1) map 요소는 방문 이력이 없는 경우 (visited[i][j] == false)에만 탐색을 수행한다.

(2) 방문한 요소에서 어떤 정보를 갖고 있는지 파악한다.

(3) 방문하지 않은 곳에서 새롭게 탐색을 시작하므로 새로운 영역이다. 영역의 수를 증가시켜준다.

(4) i, j번째 요소에 연결 된 모든 요소를 탐색할 것이다. 이 때 사용하는 함수는 dfs(깊이우선탐색)이다.

static void execute() {
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(!visited[i][j]){ - - - - - - - - - - - - - - - -(1)
                    char ch = map[i][j]; - - - - - - - - - - - - - (2)
                    numOfWood++; - - - - - - - - - - - - - - - - - (3)
                    dfs(i, j, ch); - - - - - - - - - - - - - - - - (4)
                }
            }
        }
    }

(5) base 조건 (또는 탈출 조건)이다. 방문한 요소가 이전에 방문한 요소와 같은 값인지 확인한다. 같지 않을 경우 탐색을 중단(return)한다.

탐색을 시작한다.

(6) 새롭게 방문한 요소이므로 방문 체크를 한다.

(7) 현재 요소의 값에 따라 다음 탐색할 요소의 경계값을 확인한다.

(8) (7)과 같은 역할을 한다.

 

static void dfs(int i, int j, char ch){
    if(ch != map[i][j]) { - - - - - - - - - - - - - - - - - - - - -(5)
        return;
    } else {
        visited[i][j] = true; - - - - - - - - - - - - - - - - - - -(6)
        if(ch == '-' && j+1<M){ - - - - - - - - - - - - - - - - - -(7)
            dfs(i, j+1, ch);
        }
        if(ch == '|' && i+1<N) { - - - - - - - - - - - - - - - - - (8)
            dfs(i+1, j, ch);
        }
    }
}

전체코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class baekjoon1388 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N, M, numOfWood;
    static char[][] map;
    static boolean[][] visited;

    static void input() throws IOException{
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new char[N][M];
        visited = new boolean[N][M];
        for(int i=0; i<N; i++){
            String str = br.readLine();
            for(int j=0; j<M; j++){
                map[i][j] = str.charAt(j);
            }
        }
    }

    static void execute() {
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(!visited[i][j]){
                    char ch = map[i][j];
                    numOfWood++;
                    dfs(i, j, ch);
                }
            }
        }
    }

    static void dfs(int i, int j, char ch){
        if(ch != map[i][j]) {
            return;
        } else {
            visited[i][j] = true;
            if(ch == '-' && j+1<M){
                dfs(i, j+1, ch);
            }
            if(ch == '|' && i+1<N) {
                dfs(i+1, j, ch);
            }
        }
    }

    public static void main(String[] args) throws IOException{
        input();
        execute();
        System.out.println(numOfWood);
    }
}

최적화를 위한 리팩토링

인공지능과 대화하며 최적화할 곳이 있는지 알아보았다.

인공지능의 제안

1) BufferedReader 대신 Scanner 사용

Scanner는 내부적으로 BufferedReader를 사용하기 때문에 입력 속도에서 큰 차이가 없다고 한다. 좀 더 간단한 로직으로 입력을 받을 수 있다고 한다.

 

2) DFS 재귀호출을 Stack을 이용한 반복문으로 변경

재귀호출은 언제나 스택 오버플로우의 위험이 있다.

 

3) numOfWood를 지역변수로 변경

numOfWood는 dfs 메서드 내에서만 사용되므로 전역 변수로 선언할 필요가 없다.

코드 수정

2)번과 3)번의 제안을 받아들여 코드를 수정해 보았다.

public class baekjoon1388 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N, M;
    static char[][] map;
    static boolean[][] visited;

    static void input() throws IOException{
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new char[N][M];
        visited = new boolean[N][M];
        for(int i=0; i<N; i++){
            String str = br.readLine();
            for(int j=0; j<M; j++){
                map[i][j] = str.charAt(j);
            }
        }
    }

    static int execute() {
        int numOfWood = 0;

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(!visited[i][j]){
                    char ch = map[i][j];
                    numOfWood++;
                    dfs(i, j, ch);
                }
            }
        }

        return numOfWood;
    }

    static void dfs(int i, int j, char ch){
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[]{i, j});

        while(!stack.isEmpty()){
            int[] current = stack.pop();
            int x = current[0];
            int y = current[1];

            if(x<0 || y<0 || x>=N || y>=M|| visited[x][y] || map[x][y]!=ch) continue;

            visited[x][y] = true;

            if(ch=='-' && y+1 <M){
                stack.push(new int[]{x, y+1});
            }
            if(ch=='|' && x+1 <N){
                stack.push(new int[]{x+1, y});
            }
        }
    }

    public static void main(String[] args) throws IOException{
        input();
        System.out.println(execute());
    }
}

수정 결과

왼쪽이 수정 전이고 오른 쪽이 수정 후이다. 수행 속도에서 큰 차이가 나지는 않았다.

테스트 수행결과

 

아래 첫 번째 결과가 수정전이고, 두 번째 결과가 수정후이다. 제출 결과에서도 수행 속도에서 큰 차이가 나지는 않았다.

백준 제출 결과 (수정전)

백준 제출 결과 (수정후)

배운점

• Stack을 이용해 DFS 탐색 수행하는 것 리마인드할 수 있었다.
• 변수선언에 있어서 좀 더 디테일한 고민을 해보게 되었다.