[BOJ/골드3] 2638

문제 풀이/BOJ

[BOJ/골드3] 2638 - 치즈

윤진노 2024. 4. 14. 23:28

💬 문제

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 1>

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

🔨 입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

🔨출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

👊🏻 예시 입력 1

8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

👊🏻 예시 출력 1

💡 해결

탐색을 통해 푸는 알고리즘 문제.

처음에는 AIR라는 공기층을 나타내는 배열을 만들고

공기층이 유입 되는 공간인지를 표시해두었다.

그리고, 그 배열과 visited와 Graph 3가지를 이용해서 치즈칸에서 탐색을 시작을 하여 2가지 방향 이상에서 공기층이 유입 된다면 그 치즈칸은 녹는 식으로 로직을 구성했다.

근데, 내가 말로 표현하려 해도 어려운데 코드는 더 짜기 복잡했고

답이 나오기가 쉽지 않은 로직이었다. 아마 구상대로 짜기라도 했으면 풀었을텐데 그렇지 못했다.

그래서 생각을 바꿔서 공기(0)칸에서 탐색을 시작하여,visited배열에 방문하는 횟수를 지정해주고 그 칸이 치즈칸일때는 방문한 횟수를 늘려주었다. 알고리즘이란게 가장 중요한게 방법 찾기인데 이런 부분에서 내가 제일 취약하다고 생각한다. 그냥 나는 재능이 없어보인다.

그리하여 완성된 코드는 밑에있다. 참고로 스택 오버플로우 예상해서 sys.setrecursionlimit 붙여주는것도 필수적이다.

pypy3로 제출할땐 안됐는데.. 메모리 초과가 나더만

파이썬으로 제출하니 되네 허허

👨🏻‍💻 CODE

import sys
sys.setrecursionlimit(10**7)

N, M = map(int, sys.stdin.readline().split())

Graph = [[0 for _ in range(M)] for _ in range(N)]
visited = [[0 for _ in range(M)] for _ in range(N)]

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

answer = 0


def DFS(x, y, visited, Graph):
    visited[x][y] += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M:
            if Graph[nx][ny] == 1:
                visited[nx][ny] += 1
            if Graph[nx][ny] == 0 and visited[nx][ny] == 0:
                DFS(nx, ny, visited, Graph)



for col in range(N):
    Graph[col] = list(map(int, sys.stdin.readline().split()))

while True:
    flag = 0
    DFS(0,0,visited,Graph)
    for i in range(N):
        for j in range(M):
            visited[i][j] = 0

    for i in range(N):
        for j in range(M):
            DFS(0,0,visited,Graph)

    for i in range(N):
        for j in range(M):
            if visited[i][j] >=2 and Graph[i][j] == 1 :
                Graph[i][j] = 0
                flag = 1

    if flag == 0:
        break

    answer += 1


print(answer)

💪🏻 결과

76953568

jinno123

2638

맞았습니다!!

32924

1976

Python 3 / 수정

1117

8분 전