[백준] 1388번 바닥 장식 JAVA [DFS][엄탱]

문제 링크

1388번: 바닥 장식

문제 설명

형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무판자가 필요한지 궁금해졌다. 나무판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.

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

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

예제

해설

해당문제는 DFS로 풀면 쉽게 풀리는 문제이다.
사실 이게 DFS문제로 봐야 하는지도 잘 모르겠다!ㅎㅎ

두 가지 정도만 알면 되는 것 같다.

 

1. 방문 배열을 만들어서 기존에 방문했던 타일은 표시해 주기

2. '-'는 가로 방향만 탐색, '|'는 세로 방향만 탐색

 

이 정도만 알면 쉽게 풀 수 있는 문제인 것 같다.

코드

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int answer = 0;
    public static boolean[][] visited;
    public static int x;
    public static int y;
    public static char[][] chars;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        x = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());

        visited = new boolean[x][y];

        chars = new char[x][y];

        for (int i = 0; i < x; i++) {
            String s = br.readLine();

            for (int j = 0; j < y; j++) {
                chars[i][j] = s.charAt(j);
            }
        }

        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (!visited[i][j]) {
                    if (chars[i][j] == '-') {
                        dfsWeight('-', i, j);
                    } else {
                        dfsHeight('|', i, j);
                    }
                    answer++;
                }
            }
        }

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

    private static void dfsWeight(char c, int i, int j) {
        if (c != '-') {
            return;
        }

        visited[i][j] = true;

        if (j + 1 >= y) {
            return;
        }

        dfsWeight(chars[i][j + 1], i, j + 1);
    }

    private static void dfsHeight(char c, int i, int j) {
        if (c != '|') {
            return;
        }

        visited[i][j] = true;

        if (i + 1 >= x) {
            return;
        }

        dfsHeight(chars[i + 1][j], i + 1, j);
    }
}