[백준]1388번 바닥 장식 - Java

문제

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

1388번: 바닥 장식

 

풀이

dfs로 풀었음!

 

개인적으로 이 문제의 포인트는

1. 한 방향(행 방향이든, 열 방향이든)으로만 탐색하면 되기 때문에 static으로 방향 벡터를 선언해줄 필요가 없음!
2. 재귀를 하러 들어가기 전에 현재의 칸이랑 재귀를 들어갈 칸이랑 미리 비교를 해서 들어갈지 말지 판단을 할 것!

이렇게 두 가지임!!!

 

어렵지 않게 풀었음!

더 자세한건 주석으로 ㄱㄱ

 

코드

// 1388번 바닥 장식
// https://www.acmicpc.net/problem/1388

package BAEKJOON;

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

public class Num1388_바닥장식 {
    static char[][] map;
    static boolean[][] visited;
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer 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];

        int count = 0; // 바닥 판자 개수(정답)

        // 입력
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j);
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visited[i][j]) {
                    solution(i, j, map[i][j]);
                    count++;
                }
            }
        }

        System.out.println(count);
    }

    // DFS
    public static void solution(int r, int c, char current) { // 열, 행, 현재 판자 모양
        // 이미 방문한 칸이면 return
        if (visited[r][c]) {
            return;
        }

        // 방문했으면 true로 바꿔주기
        visited[r][c] = true;

        if (map[r][c] == '-') { // -모양이면 같은 행으로 쭉
            int nc = c + 1; // 행 방향으로 탐색

            if (nc >= M) { // 범위 벗어나면 리턴
                return;
            } else {
                // 다음으로 탐색할 칸의 판자 모양이 현재 판자와 같으면 탐색 ㄱㄱ
                if (current == map[r][nc]) {
                    solution(r, nc, map[r][nc]);
                }

            }

        } else if (map[r][c] == '|') {
            int nr = r + 1; // 열 방향으로 탐색

            if (nr >= N) { // 범위 벗어나면 리턴
                return;
            } else {
                // 다음으로 탐색할 칸의 판자 모양이 현재 판자와 같으면 탐색 ㄱㄱ
                if (current == map[nr][c]) {
                    solution(nr, c, map[nr][c]);
                }
            }

        }

    }
}