[BOJ] 5212. 지구 온난화 (Python/구현/Silver 2)

---

[문제 링크] 👉https://www.acmicpc.net/problem/5212

---

풀이 방법

이 문제는 주어진 지도를 미래의 상태로 변형하고, 불필요한 바다 부분을 제거해 가장 외곽의 땅만 출력하는 문제이다.

 

1️⃣ 초기값 설정

dx = [1, 0, -1, 0]  # x(행) 
dy = [0, -1, 0, 1]  # y(열) 
future_map = [["."]*C for _ in range(R)]  # 미래 지도 생성

• 지도를 순회하면서 각 X(땅) 주위에 바다가 3칸 있으면 땅이 잠기도록 한다.
• 새로운 미래 지도를 future_map 이라고 하고, 모두 "." (바다)가 담긴 2차원 배열에 생성한다.
• dx, dy 는 상하좌우 확인에 필요한 좌표이다.

 

2️⃣ 미래 지도 생성

for x in range(R):
    for y in range(C):
        sea = 0
        if maps[x][y] == "X":  # 땅이면 주위가 바다인지 탐색
            for i in range(4):  # 주변 탐색
                nx = dx[i] + x
                ny = dy[i] + y
                if nx < 0 or nx >= R or ny < 0 or ny >= C:  # 범위를 벗어나면
                    sea += 1
                elif maps[nx][ny] == ".":  # 인접한 곳이 바다이면
                    sea += 1  # 바다 개수 카운트
            if sea < 3:  # 인접한 바다가 세 칸 미만이면
                future_map[x][y] = "X"  # 땅으로 바꾸기

 

참고 자료

• if maps[x][y] == "X":
  • 현재 지도를 탐색하다가 "X"(땅)를 만나면 주변을 탐색한다. (상하좌우 확인)
• if nx < 0 or nx >= R or ny < 0 or ny >= C:
  • 주변을 탐색하다가 지도의 범위를 벗어나면 바다 개수를 증가시킨다.
  • 지도의 범위를 벗어난다는 것은 탐색하려는 위치가 주어진 지도 위치에 없다는 말이다. 
  • 지도에 없는 칸이나 지도에 벗어나는 것은 모두 바다이기 때문에 바다의 개수를 증가시킨다.  
• elif maps[nx][ny] == ".":
  • 지도의 범위를 벗어나지 않고, 인접한 곳이 "."(바다)이면 바다 개수를 증가시킨다. 

• if sea < 3:
  • 인접한 바다가 세 칸 미만이면, 미래 지도에서 현재 위치를 "X"(땅) 으로 저장한다.

 

 

3️⃣ 미래 지도에서 땅의 영역 찾기

future_map

min_row, max_row = R, 0
min_col, max_col = C, 0

for x in range(R):
    for y in range(C):
        if future_map[x][y] == "X":
            min_row = min(min_row, x)
            max_row = max(max_row, x)
            min_col = min(min_col, y)
            max_col = max(max_col, y)

• 모든 땅(X)을 포함하는 가장 작은 직사각형 범위를 찾아 최소 및 최대 행과 열을 기록한다.
• 이를 통해 필요한 땅만 포함하는 최소 외곽 영역을 구한다.

 

4️⃣ 출력

• 위에서 찾은 최소 행부터 최대 행, 최소 열부터 최대 열 범위 내의 future_map만 출력한다.
• 불필요한 바다 부분이 제외된, 문제에서 요구하는 결과만을 보여줄 수 있다.

Solution

R, C = map(int, input().split())
maps = [input().strip() for _ in range(R)]
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
future_map = [["."]*C for _ in range(R)]

for x in range(R):
    for y in range(C):
        sea = 0
        if maps[x][y] == "X":  # 땅이면 주위가 바다인지 탐색
            for i in range(4):
                nx = dx[i] + x
                ny = dy[i] + y
                if nx < 0 or nx >= R or ny < 0 or ny >= C:  # 범위를 벗어나면
                    sea += 1
                elif maps[nx][ny] == ".":  # 인접한 곳이 바다이면
                    sea += 1  # 바다 개수 카운트
            if sea < 3:  # 인접한 바다가 세 칸 미만이면
                future_map[x][y] = "X"  # 땅으로 바꾸기

# 땅 영역의 최소, 최대 행과 열 찾기
min_row, max_row = R, 0
min_col, max_col = C, 0

for x in range(R):
    for y in range(C):
        if future_map[x][y] == "X":
            min_row = min(min_row, x)
            max_row = max(max_row, x)
            min_col = min(min_col, y)
            max_col = max(max_col, y)

# 최소, 최대 범위에 맞게 출력
for x in range(min_row, max_row + 1):
    print("".join(future_map[x][min_col:max_col + 1]))

 

 

 

👩‍💻 회고

미래 지도를 만드는 것까진 문제 없었는데 작은 직사각형으로 자를 때가 문제였다. 행 열의 최대 최소를 구하면 되겠다 생각까지 했는데 그 이상 가지 못했다. 처음엔 미래 지도에서 주변 탐색을 다시 하면서 인접한 곳에 "X"가 있으면 주변과 같이 출력하려고 했었는데, 그렇게 가면 지저분한 풀이가 나올까봐 포기했다. 다음에 다시 풀땐 어렵지 않게 풀 수 있기를!

---