BOJ 5212 지구 온난화 (Java)

문제 탐색하기

지도의 크기를 입력받고, 4방향이 바다인지 체크 후 50년 후의 새로운 지도를 출력한다. 이때 새로운 지도는 섬을 포함하는 가장 작은 직사각형 형태로 출력하도록 한다.

코드 설계하기

구현 방법

1. 입력 및 지도 초기화
   • 입력 받기: 첫 줄에서 R(행의 수)와 C(열의 수)를 읽어온다.
   • 배열 선언 및 초기화:
     • map과 newMap 배열을 12×12로 고정
     • 모든 인덱스 값을 ‘.’(바다)로 초기화하여 경계 문제를 단순화한다.
   • 지도 입력받기:
     • i=1부터 R까지 각 행에 대해 한 줄 전체를 읽은 후,
     • j=1부터 C까지 각 문자를 map[i][j]에 저장하고, 같은 값으로 newMap[i][j]도 초기 복사한다.
2. 50년 후 지도 계산 (시뮬레이션)
   • 순회: i=1부터 R, j=1부터 C까지 전체 셀을 순회한다.
   • 조건 검사:
     • 현재 셀이 ‘X’인 경우, 4방향(상, 좌, 하, 우)으로 인접한 셀을 검사한다.
     • 인접 셀이 ‘X’가 아닌(즉, 바다) 경우에 cnt를 증가시킨다.
   • 변경 조건:
     • 만약 4방향 중 3칸 이상이 바다이면, newMap[i][j]를 ‘.’로 변경하여 50년 후 잠기는 것으로 처리한다.
3. 출력 범위 결정 (최소/최대 범위 계산)
   • 범위 계산:
     • 다시 i=1부터 R, j=1부터 C까지 순회하면서, newMap[i][j]가 ‘X’인 경우
     • 해당 셀의 위치를 기준으로 minX, maxX, minY, maxY 값을 갱신하여 실제 섬이 존재하는 최소/최대 행과 열을 결정한다.
4. 출력
   • 최종 출력:
     • minX ~ maxX, minY ~ maxY 범위 내의 newMap 데이터를 BufferedWriter를 사용하여 출력한다.

시간 복잡도

1. 입력 및 초기화 단계
   • 지도 각 행을 읽어들여 각 문자에 접근 → O(R * C)
   • 배열 초기화는 (R+2)×(C+2) 크기로 진행되지만, 상수 배수이므로 O(R * C)로 볼 수 있다.
2. 50년 후 지도 계산 (시뮬레이션)
   • 전체 셀에 대해 순회 (R * C)회
   • 각 셀에서 최대 4방향 검사 → 4 * (R * C)번 연산 → O(R * C)
3. 최소/최대 범위 계산
   • 전체 셀 순회 (R * C)회, 각 셀마다 상수 시간 내에 min/max 갱신 → O(R * C)
4. 출력 단계
   • worst-case: 섬이 전체에 걸쳐 있을 경우, 출력에 R * C번 연산 → O(R * C)

모든 단계의 연산은 각 O(R * C)로 진행되므로 전체 시간 복잡도는 O(R * C)이다.

최대 연산 횟수 계산

• R, C (1 ≤ R, C ≤ 10)
• 입력/초기화: 약 R * C번 연산
• 시뮬레이션: 최대 4 * R * C번 연산 (각 셀당 4회 검사)
• 범위 계산: 최대 4 * R * C번 연산 (각 셀당 min, max 갱신 4회 정도)
• 출력: 최대 R * C번 연산

• 총합: (1 + 4 + 4 + 1) * R * C = 약 10 * R * C ≈ 1,000번 연산

  따라서 모든 경우의 수를 탐색하더라도 시간 내에 충분히 연산할 수 있다.

정답 코드 (Java)

import java.io.BufferedReader;  
import java.io.BufferedWriter;  
import java.io.InputStreamReader;  
import java.io.OutputStreamWriter;  
import java.util.Arrays;  
import java.util.StringTokenizer;  
  
public class Main {  
    private static int R, C;  
    private static char[][] map = new char[12][12];  
    private static char[][] newMap = new char[12][12];  
  
    private static int[] dx = {-1, 0, 1, 0};  
    private static int[] dy = {0, -1, 0, 1};  
  
    private static int minX = 11, minY = 11;  
    private static int maxX = 0, maxY = 0;  
  
    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());  
        R = Integer.parseInt(st.nextToken());  
        C = Integer.parseInt(st.nextToken());  
  
        // 초기화  
        for (int i = 0; i < 12; i++) {  
            Arrays.fill(map[i], '.');  
            Arrays.fill(newMap[i], '.');  
        }  
  
        // 지도 입력받기  
        for (int i = 1; i <= R; i++) {  
            String line = br.readLine();  
            for (int j = 1; j <= C; j++) {  
                map[i][j] = line.charAt(j - 1);  
                newMap[i][j] = map[i][j];  
            }  
        }  
  
        // 50년 후 지도 계산  
        for (int i = 1; i <= R; i++) {  
            for (int j = 1; j <= C; j++) {  
                if (map[i][j] == 'X') {  
                    int cnt = 0;  
                    for (int k = 0; k < 4; k++) {  
                        int nx = i + dx[k];  
                        int ny = j + dy[k];  
                        if (map[nx][ny] != 'X') cnt++;  
  
                    }  
  
                    if (cnt >= 3) {  
                        newMap[i][j] = '.';  
                    }  
                }  
            }  
        }  
  
        // 최대~최소 범위 계산  
        for (int i = 1; i <= R; i++) {  
            for (int j = 1; j <= C; j++) {  
                if (newMap[i][j] == 'X') {  
                    minX = Math.min(minX, i);  
                    maxX = Math.max(maxX, i);  
                    minY = Math.min(minY, j);  
                    maxY = Math.max(maxY, j);  
                }  
            }  
        }  
  
        // 출력  
        for(int i=minX; i<=maxX; i++){  
            for(int j=minY; j<=maxY; j++){  
                bw.write(newMap[i][j]);  
            }  
            bw.newLine();  
        }  
  
        bw.flush();  
        bw.close();  
        br.close();  
    }  
}