1. 빙산

https://www.acmicpc.net/problem/2573

처음에 보기에는 쉬웠던 문제였으나 푸는 과정에서 상당히 애를 먹었던 문제였다.

보자마자 든 생각은 일전의 미로, 뱀 같은 문제처럼 0 이 아닌 좌표 주변의 값을 비교하여 값이 0 이면 해당 좌표값의 수를 -1 시키고 얼음덩어리의 수를 새면 되는 비교적 간단한 문제라는 생각이 들었다.

다만, 해당하는 문제를 풀면서 생겼던 문제점은 2가지였는데 한가지는 처음에 주변 좌표의 값을 비교하여 0 이 되는 순간, 주변의 다른 빙산이 해당 년도에 원래 녹을 값보다 추가로 1 이 낮아지게 되기 때문에 본래의 답에 도달하지 못한다는 점이었다.

이 경우 최초 내 식에서는 dfs 를 사용하여 다른 좌표값들을 방문했다는 것을 표식으로 하여 0 이 아닌 좌표에만 방문을 했다는 체크를 하고 -1 을 하는 과정에서 방문을 하지 않은 좌표의 값이 0 일때만 -1 을 하도록 하는것으로 해결하였다.

다른 경우는 0 이 아닌 좌표의 값들을 가져오고 해당하는 좌표의 값들만 -1 을 시키는 방법으로 해결하는 경우도 있었다.

두번째로는 빙하가 어떻게 2개가 되었는지 파악해야할지 생각이 안난다는 점이었다.

dfs 함수가 도는 조건으로 하거나 혹은 따로 빙하의 갯수를 체크하는 함수를 만들어 체크해보려 하였으나 코드를 잘못짠건지 제대로 체크가 되지 않았다. 조건문의 문제인듯 한데 인터넷에서 해당하는 부분을 참고하여 보아도 사실상 이 부분은 나랑 비슷한데도 내 코드에서는 제대로 돌아가지 않아서 아마 1번 부분과 같이 하여 수정해야 했던것 같은데 결국 스스로의 힘으로 풀어내지 못하고 문제의 답을 찾아내어 코드를 수정 할 수 밖에 없었다.

import sys
sys.stdin = open("input.txt", "r")
sys.setrecursionlimit(10 ** 4)
input = sys.stdin.readline

n, m = map(int, input().split())
ice = [list(map(int, input().split())) for _ in range(n)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

year = 0

while True:
    year += 1
    count_water = [[0 for _ in range(m)] for _ in range(n)]

    for i in range(n):
        for j in range(m):
            if ice[i][j] > 0:
                for k in range(4):
                    nx = i + dx[k]
                    ny = j + dy[k]
                    if 0 <= nx < n and 0 <= ny < m:
                        if ice[nx][ny] == 0:
                            count_water[i][j] += 1

    for i in range(n):
        for j in range(m):
            if ice[i][j] > 0:
                ice[i][j] -= count_water[i][j]
                if ice[i][j] < 0:
                    ice[i][j] = 0

    visited = [[False] * (m) for _ in range(n)]
    cnt = 0

    for i in range(n):
        for j in range(m):
            if not visited[i][j] and ice[i][j] != 0:
                visited[i][j] = True
                arr = [[i, j]]
                while arr:
                    p = arr.pop()
                    for q in range(4):
                        nx, ny = dx[q] + p[0], dy[q] + p[1]
                        if 0 <= nx < n and 0 <= ny < m:
                            if ice[nx][ny] == 0:
                                if not visited[nx][ny] and ice[i][j] > 0:
                                    cnt += 1
                                    visited[nx][ny]

    if cnt > 1:
        break

    total = 0
    for i in ice:
        total += sum(i)

    if total == 0:
        print(0)
        exit()
print(year)

여담이지만 내 나쁜 습관중 하나는 코드가 돌아가지 않으면 통째로 지워버리는것이 프로그래밍 에서 가장 좋지 않은 습관이지 않나 싶다.
최소한 Github 에다가 올려두기만 해도 나중에 언젠가는 수정해서 될지도 모를텐데...

2. 토마토 (7576, 7569)

https://www.acmicpc.net/problem/7576

https://www.acmicpc.net/problem/7569

토마토 문제의 경우 동일한 이름으로 2개가 있었다. 차이는 2차원이냐 3차원이냐의 차이.
이름정도는 토마토 1 , 2 정도로 바꿔주는게 좋았을것 같다는 생각이 든다.

떄문에 처음 7576( 2차원 토마토 ) 문제를 풀고 나서 3차원 토마토 (7569) 를 풀려고 생각했기 때문에 처음에 7576 쪽을 먼저 풀게 되었다.

토마토 문제 자체는 빙산보다 먼저 풀었기에 토마토를 풀었던 경험이 빙산을 풀때의 접근에 도움이 되었다.

일단, 전체 좌표에서 값이 1 인 좌표를 찾고 해당 하는 좌표의 주변값을 비교하여 0 인 것이 있으면 1 로 바꾸고 -1 은 그대로 둔다. 해당 하는 방식으로 해당하는 리스트의 모든 값이 1 이 되면 1이 될때까지 시행한 횟수를, 더이상 1로 변경 할 수 없다면 -1 을 출력하는것을 기본 토대로 잡았다.

해당하는 방식대로 작성하는것은 어려운것은 아니었고, 해당하는 코드를 기반으로 하여 3차원의 토마토도 풀 생각이었으나 그건 쉬운일은 아니었다.

from collections import deque
import sys

m, n = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
queue = deque([])
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
res = 0

for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1:
            queue.append([i, j])


def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] == 0:
                matrix[nx][ny] = matrix[x][y] + 1
                queue.append([nx, ny])


bfs()
for i in matrix:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    res = max(res, max(i))
print(res - 1)

bfs 통하여 문제를 풀었고 해당하는 풀이는 deque 를 이용하여 풀었다.

이 문제 코드를 통하여 3차원 토마토 문제를 풀려고 하였으나 바로 푸는것은 실패하였다.

3차원 토마토의 경우 2차원 토마토의 코드에서 특정값을 * 2 만 해주면 답이 나올것이라는 단순한 생각을 하였는데 틀렸다.

다만, 방법이 단순했던것은 맞는데 dx, dy 처럼 3차원을 확인하는 dz 리스트를 만들고 안의 요소를 4개에서 6개로 하여 체크하여 끝...방법을 알고나니 너무 허무한 해결법이었다.