치즈
solved_ac[Class4][치즈](https://www.acmicpc.net/problem/2638)
문제
N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.
<그림 1>
<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.
<그림 2>
<그림 3>
모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 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
4문제 해석
[백준]1260번: DFS와 BFS의 업그레이드 문제이다. 앞서 풀었던 미로찾기와 비슷한데 여기서 추가된 것은 벽을 한번은 뚫을 수 있다는 것이다. 무조건 한번을 뚫어야 되는 것이 아닌 필요에 의해서 뚫을수도 있고 안뚫을수도 있다는 얘기이다. 이게 많이 복잡하다. 여기서 key 포인트는 벽을 안뚫고 갈때와 벽을 뚫고 갈때를 구분해서 작성을 해야 된다는 것이다. 그리고 또한 미로찾기에서는 graph를 직접 업데이트 해가면서 마지막 배열의 값이 총 걸리는 거리를 의미했는데 여기서는 graph를 직접 업데이트 시켜주면 안된다. 방문한 곳의 숫자가 증가해 있어서 이걸 벽으로 보고 못 지나갈 수 있기 때문에 다른 리스트를 이용하여 업데이트 시켜줘야한다. 그리고 또한 정답을 출력할 때 visited 리스트를 루프를 돌아 0이 아닌 리스트를 찾아 맨 마지막 리스트의 값을 출력할 필요가 없다. 어차피 최단 경로이기 때문에 bfs 루프를 돌다가 queue에서 가장 먼저 popleft()가 되어 나오는 좌표가 맨 오른쪽 밑의 좌표와 같다면 그것이 가장 최단 경로의 좌표인 것이다. 하지만 bfs 루프를 전부 돌았는데도 아무것도 return이 되는 것이 없다면 끝의 좌표에 도달하지 못한것이기 때문에 -1을 return 해주면서 정답을 도출해내면 된다.
풀이
- 치즈가 없는건 0 치즈가 있는건 1이다.
- 첫줄부터 bfs 시작
- 1인걸 찾았다면 치즈가 있다는 것이기 때문에 0(외부공기)의 입장에서 치즈와 한번 만난거임. 그렇다면 graph 값을 1 더해줌.
- 그렇게 쭉 탐색하면서 1시간에 녹는 치즈들은 최소 2번이상 외부랑 닿아
있으니깐 3이상이 될꺼임. - 그러면 루프를 돌면서 배열 체크하면서 3이상인걸 찾아서 0(외부)으로 만듬.
- 다 돌면 루프 한번 돌았을때 1시간이 지났으니 시간을 1시간 올려줌.
- 그리고 다시 루프 돌면서 bfs 다시 호출
- 그러면 또 외부 입장에서 치즈들이 양 측으로 닿아있는거 체크
전체 골격
- 무한 루프
- bfs 호출
- 치즈가 아닌 곳에서 치즈와 마주보고 있는 곳을 이용해 치즈 graph를 1씩 상승시켜주기 위함. 애초에 치즈 그래프에서 치즈가 있는 곳은 1이기 때문에 만약 외부와 2곳 이상 닿아 있으면 3이 넘어가게 됨.
- N만큼 루프
- M만큼 루프
- 방문 여부를 위한 visited 리스트를 돌면서 0으로 초기화
- 만약 graph의 값이 3이상이 넘어간다면?
- 외부와 2곳 이상 노출되어 있다는 뜻.
- graph의 값을 0으로 초기화. 왜냐하면 치즈는 없어졌기 때문에 외부가 됨.
- 탈출 flag인 exit_check 1로 업데이트 - 적어도 1개의 치즈는 녹아서 없어진 것이기 때문에 무한 루프 탈출을 위해 exit_check라는 flag를 1로 변경
- 해당 좌표 queue에 append
- 이곳도 외부가 된 것이기 때문에 queue에 집어넣어서 다음 bfs에서 씀.
- 만약 graph의 값이 2라면?
- 외부와 1곳 노출되어 있어서 치즈가 녹지 않기 때문에 다시 1로 초기화
- M만큼 루프
- 탈출을 위한 flag인 exit_check가 1이라면?
- 적어도 1개 이상의 치즈가 녹았기 때문에 1시간이 지났다. 그래서 count를 1개 올려준다.
- 만약 flag값이 1이 아니라면?
- 더 이상 녹일 치즈가 없어서 count를 출력해주고 탈출
- 탈출하지 않았다면 더 녹일 치즈가 있을 수도 있기 때문에 flag값을 0으로 초기화
- bfs 함수
- queue가 빌때까지
- 좌표 popleft()
- 상, 하, 좌, 우 검색을 위해 4번 루프
- index가 해당 범위안에 해당한다면?
- graph 값이 1보다 크거나 같고 visited가 1보다 작거나 같다면?
- 왜 1보다 작거나 같냐고 물어봤냐면 만약 치즈와 닿아 있는 외부가 3곳 이상 외부와 닿아있다면 총 3번 방문하게 된다. 그렇다면 치즈를 총 3번 값을 올려주게 되는데 이러면 반례가 나온다. 그래서 딱 1번 방문했을때 visited값은 1이여서 그때만 graph의 값을 1 올려주고 visited 값을 1 올려준다. 그러면 나머지 2번이 방문을 하게 되더라도 visited 값을 미리 1 올려놨기 때문에 1보다 크게 되서 graph 값을 중복으로 다시 올려주지 않을 수 있다.
- graph의 값을 1 올려준다.
- 만약 방문한 적이 없고, graph의 값이 0이라면?
- 외부이기 때문에 다음 검사를 위해 queue에 append
- 방문을 했으니 1 증가
- 현재 있는 위치는 치즈와 닿아 있는 부분을 한번 체크했기 때문에 현재 위치를 1 증가시켜줘서 중복 치즈 체크를 방지한다.
- queue가 빌때까지
import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
graph = [[0] * M for _ in range(N)]
visited = [[0] * M for _ in range(N)]
for i in range(N):
graph[i] = list(map(int, sys.stdin.readline().split()))
queue = deque()
queue.append([0, 0])
visited[0][0] = 0
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
def bfs():
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= 0 and nx < N and ny >= 0 and ny < M:
if graph[nx][ny] >= 1 and visited[x][y] <=1:
graph[nx][ny] += 1
elif visited[nx][ny] == 0 and graph[nx][ny] == 0:
queue.append([nx, ny])
visited[nx][ny] = 1
visited[x][y] += 1
count = 0
exit_check = 0
while True:
bfs()
for i in range(N):
for j in range(M):
visited[i][j] = 0
if graph[i][j] >= 3:
graph[i][j] = 0
exit_check = 1
queue.append([i, j])
elif graph[i][j] == 2:
graph[i][j] = 1
if exit_check == 1:
count += 1
else:
print(count)
break
exit_check = 0고찰
bfs를 시작할때 어떤 것을 기준으로 할지 중요하게 생각하게 되었다. 처음에는 치즈를 기준으로 bfs를 시작했었는데 코드가 너무 난잡해지고 조건이 많아져서 외부를 기준으로 bfs를 하였다. 그렇게 하고 하니 내부 공기를 굳이 신경 쓰지 않더라도 알아서 치즈가 막아주기 때문에 bfs가 내부 공기가 있는 곳으로 들어가서 검사를 하지 않았다. 그리고 한타임이 지나면 치즈들이 녹아 없어지는데 그곳에도 많은 조건이 숨겨져 있었다. 풀기 전에 모든 조건을 완벽하게 글로 써서 슈도 코드를 작성하고 코딩을 해야겠다..
