99클럽 코테 스터디 13일차 TIL [DFS]

- 오늘의 학습 키워드 : DFS

[문제 이름 : 미로 보수 (백준 30689, G3)]
문제 url : https://www.acmicpc.net/problem/30689

내가 작성한 코드는 아래와 같다.

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static char[][] map;
    static int[][] cost;
    static int[][] count;
    static boolean[][] visited;
    static List<Integer> results = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(stringTokenizer.nextToken());
        M = Integer.parseInt(stringTokenizer.nextToken());

        map = new char[N][M];
        cost = new int[N][M];
        count = new int[N][M];
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            map[i] = bufferedReader.readLine().toCharArray();
        }

        for (int i = 0; i < N; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for (int j = 0; j < M; j++) {
                cost[i][j] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }

        int answer = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visited[i][j]) DFS(i, j);
                if (!results.isEmpty()) answer += initMiro();
            }
        }

        System.out.println(answer);
    }

    private static void DFS(int x, int y) {
        if (x < 0 || y < 0 || x >= N || y >= M || count[x][y] == 2) {
            return ;
        }

        if (!visited[x][y]) {
            count[x][y] += 1;
            switch (map[x][y]) {
                case 'U':
                    DFS(x - 1, y);
                    break;
                case 'D':
                    DFS(x + 1, y);
                    break;
                case 'L':
                    DFS(x, y - 1);
                    break;
                case 'R':
                    DFS(x, y + 1);
                    break;
            }
            visited[x][y] = true;

            if (count[x][y] == 2) {
                results.add(cost[x][y]);
                count[x][y] = 1;
            }
        }
    }

    private static int initMiro() {
        int min = Integer.MAX_VALUE;
        for (int cost : results) {
            if (cost < min) {
                min = cost;
            }
        }

        results.clear();
        return min;
    }
}

풀이 과정 (풀이 시간 : 1시간)

1. 주어진 미로 정보를 이차원 배열에 저장한다.

2. 미로 정보에 따라 상하좌우로 움직일 수 있으므로, 각 칸에서 배열 전체를 DFS로 탐색하며 중복 칸 수를 확인한다.

3. count[x][y] == 2인 경우가 반복되는 장소이며, 2번 움직인 장소들의 보수 비용을 list로 체크해준 뒤, 다음 번 확인에 중복되지 않게 고친 곳은 count[x][y]=1로 변경해준다.

4. 반복되는 구간의 list에서 보수 비용의 최소 값들을 더해 비용을 계산한다.

내일은 NCS 관련 공부를 진행해볼 예정이다.