백준 1388 - 바닥 장식 (자바 - 그래프)

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

1388번: 바닥 장식

 

* 문제 요약

형택이는 건축가이다. 지금 막 형택이는 형택이의 남자친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다.

나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.

이제 '-' 와 '|' 로 이루어진 바닥 장식모양이 주어진다. 만약 두 개의 '-' 가 인접해있고, 같은 행에 있다면 두 개는 같은 나무 판자이고, 두 개의 '|' 가 인접해있고, 같은 열에 있다면 두 개는 같은 나무 판자이다.

기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 갯수를 출력하는 프로그램을 작성하시오.

 

* 입력

첫째 줄에 방 바닥의 세로 크기 N과 가로 크기M이 주어진다. 둘째 줄부터 N개의 줄에 M개의 문자가 주어진다.

이것은 바닥 장식모양이고, '-' 와 '|' 로만 이루어져 있다.

N과 M은 50이하인 자연수이다.

 

* 출력

첫째 줄에 문제의 정답을 출력한다.

 

* 예시

 

* 해결 과정

바닥 장식의 상태를 2차원 배열에 입력받은 다음 이중반복문을 다음과 같이 수행해준다.

1. visited 배열에서 현재 탐색중인 인덱스 값이 true 인 경우 이미 탐색을 마친 위치라는 뜻이므로 다음 반복으로 넘어간다.

2. 그렇지 않을 경우 2차원 배열에서 현재 인덱스 값이 '-' 인지 '|' 인지 확인한다.

3. '-' 일 경우 dfs() 메소드를 수행하되, 매개변수로 true 를 전달하여 '-' 를 연속적으로 탐색해야함을 전달한다.

4. '|' 일 경우 dfs() 메소드를 수행하되, 매개변수로 false 를 전달하여 '|' 를 연속적으로 탐색해야함을 전달한다.

 

dfs() 메소드의 경우 다음과 같이 로직을 수행한다.

1. visited 배열에서 메소드의 매개변수를 통해 전달받은 인덱스에 해당하는 값을 true로 초기화하여 현재 인덱스를 방문 표시해준다.

2. 매개변수로 true 를 전달받은 경우 현재 행을 기준으로 '-' 가 얼마나 연속되는지 확인해야 하므로 i, j 중 열 인덱스 정보를 나타내는 j를 1 늘린 후, 조건문을 통해 현재 j가 최대 열 갯수 m보다 작고 2차원 배열에서 (i, j) 인덱스에 해당하는 값이 '-' 인 경우 dfs() 메소드를 재귀적으로 호출하여 '-' 가 현재 행을 기준으로 어디까지 연속되는지 메소드 호출 스택을 쌓아가며 확인해준다. (매개변수는 계속해서 true 를 함께 전달해준다.)

만약 (i, j) 인덱스에 해당하는 값이 '|' 인 경우 dfs() 메소드 재귀 호출을 중단하고 스택을 쌓아가며 호출했던 메소드들을 하나씩 하나씩 종료시켜서 dfs() 메소드가 처음으로 호출된 이중반복문으로 돌아간다.

3. 매개변수로 false 를 전달받은 경우 현재 열을 기준으로 '|' 가 얼마나 연속되는지 확인해야 하므로 i, j 중 행 인덱스 정보를 나타내는 i 를 1 늘린 후, 조건문을 통해 현재 i가 최대 행 갯수 n보다 작고 2차원 배열에서 (i, j) 인덱스에 해당하는 값이 '-' 가 아닌 경우. 즉, '|' 인 경우 dfs() 메소드를 재귀적으로 호출하여 '|' 가 현재 열을 기준으로 어디까지 연속되는지 메소드 호출 스택을 쌓아가며 확인해준다. (매개변수는 계속해서 false 를 함께 전달해준다.)

만약 (i, j) 인덱스에 해당하는 값이 '-' 인 경우 dfs() 메소드 재귀 호출을 중단하고 스택을 쌓아가며 호출했던 메소드들을 하나씩 하나씩 종료시켜서 dfs() 메소드가 처음으로 호출된 이중반복문으로 돌아간다.

4. 각 경우에서 재귀 호출을 끝낸 뒤 이중반복문으로 돌아왔다면 '-' 나 '|' 로 연속적으로 이어진 나무 판자의 각 지점에 대한 방문이 끝났다는 뜻이므로 나무 판자의 갯수 (count) 를 1 늘려준다. 

 

이중반복문이 끝나고 나면 반복문 내부에서 값이 증가된 (또는 증가되지 않은) count 값을 출력시켜 준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    static int n, m;
    static char[][] floorArray;
    static boolean[][] visited;

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);

        floorArray = new char[n][m];
        visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            char[] rowArray = br.readLine().toCharArray();
            floorArray[i] = rowArray;
        }

        // '-' 를 탐색할 경우 true, '|' 를 탐색할 경우 false 를 매개변수로 전달
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (visited[i][j])
                    continue;
                if (floorArray[i][j] == '-')
                    dfs(i, j, true);
                else
                    dfs(i, j, false);
                count++;
            }
        }

        bw.write(count + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private void dfs(int i, int j, boolean check) {
        visited[i][j] = true;
        if (check) {
            j++;
            if (j < m && floorArray[i][j] == '-')
                dfs(i, j, true);
        } else {
            i++;
            if (i < n && floorArray[i][j] != '-')
                dfs(i, j, false);
        }
    }
}

 

굉장히 오랜만에 풀어본 그래프 문제(dfs) 라서 그런지 기본적으로 어떤식으로 풀어야 하는지 완전히 까먹어버린 바람에 결국 직접 답을 찾아보고 문제를 풀었다.

다시 한번 그래프 문제를 계속 풀어나가면서 잃어버린 그래프 문제풀이 노하우를 쌓아나가야 할 것 같다.