[랜덤 마라톤] Decision(7873)

1. 문제 풀이 아이디어

• 타일의 종류에 따라 연결 가능한 방향을 확인하고, 다음 타일이 연결될 수 있는지 판단하여 BFS나 DFS를 사용하면 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    static int n;
    static int m;
    static char[][] map;
    static boolean[][] visited;
    static int result;
    static Map<Character, char[]> dirc = new HashMap<>();
    static Map<Character, int[]> diri = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        int z = Integer.parseInt(bufferedReader.readLine());
        dirc.put('B', new char[]{'L', 'D'});
        dirc.put('C', new char[]{'L', 'U'});
        dirc.put('D', new char[]{'R', 'U'});
        dirc.put('E', new char[]{'R', 'D'});
        dirc.put('F', new char[]{'L', 'R', 'U', 'D'});
        diri.put('L', new int[]{0, -1});
        diri.put('R', new int[]{0, 1});
        diri.put('U', new int[]{-1, 0});
        diri.put('D', new int[]{1, 0});
        for (int i = 0; i < z; i++) {
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            n = Integer.parseInt(stringTokenizer.nextToken());
            m = Integer.parseInt(stringTokenizer.nextToken());
            map = new char[n][];
            visited = new boolean[n][m];
            result = 0;
            for (int j = 0; j < n; j++) {
                String line = bufferedReader.readLine();
                map[j] = line.toCharArray();
            }
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    if (visited[j][k]) continue;
                    visited[j][k] = true;
                    if (map[j][k] == 'A') continue;
                    bfs(j, k);
                }
            }
            stringBuilder.append(result).append('\n');
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }

    private static void bfs(int j, int k) {
        result++;
        Queue<int[]> que = new ArrayDeque<>();
        que.add(new int[]{j, k});
        while (!que.isEmpty()) {
            int[] cur = que.poll();
            char c = map[cur[0]][cur[1]];
            for (Character dc : dirc.get(c)) {
                int x = cur[0] + diri.get(dc)[0];
                int y = cur[1] + diri.get(dc)[1];
                if (x < 0 || y < 0 || x >= n || y >= m) continue;
                if (visited[x][y]) continue;
                char nc = map[x][y];
                if (nc == 'A') continue;
                if (dc == 'L')
                    if (nc == 'B' || nc == 'C') continue;
                if (dc == 'R')
                    if (nc == 'D' || nc == 'E') continue;
                if (dc == 'U')
                    if (nc == 'C' || nc == 'D') continue;
                if (dc == 'D')
                    if (nc == 'B' || nc == 'E') continue;
                visited[x][y] = true;
                que.add(new int[]{x, y});
            }
        }
    }
}

3. 정리

• dirc 맵에 타일별 연결 가능한 방향을 저장한다.

• diri 맵에 각 방향에 따른 좌표 이동값을 저장한다.

• BFS를 구현할 때 Queue를 사용하여 인접한 타일을 탐색하며, visited 배열로 탐색한 타일을 체크한다.

• 다음 타일의 종류를 변수 nc에 저장하고, 현재 탐색 방향인 dc와 비교하여 이동 가능 여부를 판단한다.

• BFS를 수행할 때마다 result를 증가시켜 최종 결과값을 구한다.

4. 다른 아이디어

• 다음 타일의 종류와 현재 탐색 방향을 비교하는 부분에서, 다른 자료구조를 사용했다면 코드가 더 깔끔해졌을 것 같다는 생각이 든다.

• 삼차원 배열이나 다른 방식을 활용했다면 더욱 정리된 형태로 구현할 수 있었을 것 같다.