2234 - 성곽 (Java)

🔗 문제 링크

---

📝 문제 설명

성곽 문제는 각 칸에 4방향(서, 북, 동, 남)의 벽이 있는 성곽이 주어지고,
이 성곽에서 다음 세 가지를 구하는 문제임:

1. 전체 방의 개수
2. 가장 넓은 방의 크기
3. 벽 하나를 제거했을 때 얻을 수 있는 가장 넓은 방의 크기

각 칸의 숫자는 벽의 유무를 비트로 표현하는데,
예를 들어, 1, 2, 4, 8은 각각 서, 북, 동, 남쪽 벽을 의미함.
인접한 칸들에서 벽이 없으면 같은 방에 속한다고 볼 수 있음.

---

✅ 접근 방식 및 시도한 방법들

첫 번째 시도: 하나의 DFS로 모든 답 도출 (시간초과 발생) ⏱️

• 아이디어:
  • 하나의 DFS를 사용하여 동시에 방의 크기, 방 번호, 그리고 "벽을 제거한 경우"의 크기까지
    모두 계산하려 함.
• 문제점:
  • 예를 들어, A 구역과 B 구역이 서로 벽으로 붙어있는 상황에서,
    A 구역의 DFS 도중에 벽을 제거해 B 구역을 탐색하는 경우가 발생하고,
    이후 B 구역에서도 같은 벽을 또 한 번 탐색하게 되어 중복 연산이 발생함.
  • 이로 인해 중복 탐색이 많아져 시간초과가 발생함.

---

두 번째 시도: 방 단위로 분리해서 처리 (성공) 🎉

• 아이디어:

  1. 방 번호와 크기 기록하기

     • 각 방에 대해 별도의 DFS를 수행하여,
       방의 개수와 해당 방의 크기를 구함.
     • 각 칸에 해당 방 번호를 기록한 numberMap을 관리하고,
       각 방의 크기는 cntByNumber 리스트에 저장함.

  2. 벽 제거 시 방 합치기

     • 모든 칸을 순회하면서 4방을 체크함.
     • 만약 인접 칸이 다른 방에 속해 있다면,
       두 방의 크기를 합친 값이 벽을 제거했을 때 얻을 수 있는 방의 크기가 됨.
     • 이때, 해당 방향에 실제 벽이 존재하는지를
       (map[i][j] & (1 << k)) == (1 << k) 조건으로 판별함.

• 장점:

  • 각 방을 한 번씩만 탐색하기 때문에 중복 DFS를 방지할 수 있음.
  • 벽을 제거한 경우에는 미리 구한 방 크기 정보를 이용해
    간단하게 두 방의 크기를 합산할 수 있음.

---

🔍 최종 코드

아래 코드는 두 번째 시도를 반영한 최종 솔루션입니다:

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

public class Main {
    private static StringTokenizer st;
    private static StringBuilder sb = new StringBuilder();
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static int N, M;
    private static int[][] map;
    private static boolean[][] visited;
    private static int[][] dir = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    private static int roomCnt, maxRoomSize, removedWallMaxRoomSize;
    private static int cntTmp;

    private static int[][] numberMap;
    private static List<Integer> cntByNumber = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        setting();
        // 각 방에 대해 DFS 실행하여 방 번호와 크기 기록
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (visited[i][j]) continue;
                roomCnt++;
                getRoomCntDfs(i, j, roomCnt - 1);
                cntByNumber.add(cntTmp);
                maxRoomSize = Math.max(maxRoomSize, cntTmp);
                cntTmp = 0;
            }
        }
        
        // (디버깅용) 방 번호 출력
//        for (int i = 0; i < N; i++) {
//            for (int j = 0; j < M; j++) {
//                System.out.print(numberMap[i][j]);
//            }
//            System.out.println();
//        }
//        System.out.println(cntByNumber);
        
        // 모든 칸에 대해 4방 탐색, 인접한 두 방이 다르면 벽 제거 시 합칠 수 있는 방 크기 계산
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                for (int k = 0; k < 4; k++) {
                    int dx = i + dir[k][0];
                    int dy = j + dir[k][1];
                    if (dx < 0 || dx >= N || dy < 0 || dy >= M) continue;
                    if (numberMap[i][j] == numberMap[dx][dy]) continue;
                    if ((map[i][j] & (1 << k)) == (1 << k)) {
                        removedWallMaxRoomSize = Math.max(
                            removedWallMaxRoomSize, 
                            cntByNumber.get(numberMap[i][j]) + cntByNumber.get(numberMap[dx][dy])
                        );
                    }
                }
            }
        }
        sb.append(roomCnt).append("\n")
          .append(maxRoomSize).append("\n")
          .append(removedWallMaxRoomSize);
        System.out.println(sb.toString());
    }

    // DFS를 통해 하나의 방에 속하는 칸의 수와 방 번호를 기록함
    private static void getRoomCntDfs(int x, int y, int number) {
        cntTmp++;
        visited[x][y] = true;
        numberMap[x][y] = number;
        for (int i = 0; i < 4; i++) {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            if (dx < 0 || dx >= N || dy < 0 || dy >= M) continue;
            if (visited[dx][dy]) continue;
            if ((map[x][y] & (1 << i)) == (1 << i)) continue;  // 해당 방향에 벽이 있다면 진행하지 않음
            getRoomCntDfs(dx, dy, number);
        }
    }

    private static void setting() throws IOException {
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M];
        numberMap = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
}

---

✅ 코드 로직 상세 설명

1. 방 탐색 (DFS) 및 방 번호 부여

   • visited 배열을 이용해 각 칸을 한 번씩만 탐색합니다.
   • DFS를 통해 인접한 칸(벽이 없는 경우)들을 하나의 방으로 묶고,
     해당 방의 크기를 cntTmp에 누적합니다.
   • 각 방에 대해 고유 번호를 numberMap에 기록하며,
     cntByNumber 리스트에 각 방의 크기를 저장합니다.
   • 이를 통해 전체 방의 개수와 가장 넓은 방의 크기를 구할 수 있음.

2. 벽 제거 시 방 합치기

   • 모든 칸을 순회하면서 4방(서, 북, 동, 남)을 검사합니다.
   • 만약 현재 칸과 인접 칸이 서로 다른 방에 속해 있고,
     현재 칸의 해당 방향에 벽이 존재하면,
     두 방을 합쳤을 때의 방 크기를 계산합니다.
   • 계산된 값 중 최댓값을 removedWallMaxRoomSize에 업데이트합니다.

3. 최종 결과 출력

   • 최종적으로, 전체 방의 개수, 가장 넓은 방의 크기,
     벽 하나를 제거해서 얻을 수 있는 최대 방 크기를 출력합니다.

---

📌 결론

• 첫 번째 시도 (하나의 DFS로 모든 것을 처리):
  • 한 번의 DFS로 방의 크기와 벽 제거 효과까지 동시에 계산하려 하였으나,
    중복 탐색으로 인해 시간 초과가 발생함.
• 두 번째 시도 (방 단위로 분리하여 처리):
  • 각 방에 대해 별도의 DFS를 수행하고, 방 번호와 크기를 기록한 후,
    전체 칸을 순회하며 벽 제거 시 합쳐질 방의 크기를 계산하는 방식으로
    중복 연산을 제거하여 효율적으로 문제를 해결함.