Python3
문제
https://www.acmicpc.net/problem/2636
키워드
- 그래프
문제 풀이
문제 요구사항
- 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈 조각이 놓여 있는 칸의 개수를 구하는 프로그램
- 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.
- 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다.
- 세로와 가로의 길이는 최대 100
변수 및 함수 설명
- n, m : 치즈 판의 세로, 가로 길이
- ans : 매 시간마다 치즈가 녹는 양을 기록하는 배열
- cnt : 매 시간마다 치즈가 녹는 양
- bfsQueue : bfs 큐
- adjMatrix : 치즈 판 (2차원 배열)
- visited : 방문처리하는 2차원 배열
- dy, dx : 상하좌우
- currentLocation : 현재 위치 튜플
- curY, curX : 현재 y, x좌표
- ny, nx : 다음 이동할 y, x좌표
풀이
BFS
인접 행렬 adjMatrix
(0, 0)부터 bfs 탐색하면서 치즈를 만나면 녹인다.
큐에 치즈가 아닌 공기 넣기 !
(입력 및 선언)
- 치즈 판의 크기를 입력받는다
- 치즈 판을 입력받는다
(bfs 함수)
- cnt를 0으로 초기화시킨다
- 큐에 원소가 들어 있을 때까지 반복한다.
- 큐의 첫 번째 원소를 빼 현재 위치를 나타내는 변수 currentLocation에 저장한다.
- 총 4번 반복한다 (상하좌우)
- 다음 이동할 칸의 좌표는 현재 위치에 dy[i], dx[i]를 더한 값이다.
- 다음 이동할 칸은 맵 안에 위치하고, 방문 처리가 되어 있지 않아야 한다.
- 만약 다음 이동할 칸이 '공기'라면(adjMatrix[ny][nx] == 0), 방문 처리를 해주고 큐에 해당 튜플을 넣는다.
- 만약 다음 이동할 칸이 '치즈'라면(adjMatrix[ny][nx] == 1), 방문 처리를 하고 치즈판은 0으로 바꾼다. (녹이는 과정..)
- 그리고 녹는 양을 세는 변수 cnt 값을 하나 증가시킨다.
- 치즈를 다 녹이면, ans 배열에 cnt 값을 넣고 cnt를 반환한다.
(녹는 시간을 구하자)
- 무한 반복문을 돌 것이다. 종료 조건은 cnt에 0이 되면, 즉 더 이상 녹일 치즈가 없으면 반복문을 빠져나올 것이다.
- 방문 처리를 매번 초기화시킨다. (초기화 시키지 않으면 두 번째 치즈판부터 방문처리가 꼬이게 된다.)
- (0, 0)부터 탐색을 시작한다. 방문 처리하고 큐에 넣고..
- bfs함수를 호출한다
(최종 출력)
- 치즈가 녹는 총 시간을 구하고, 모두 녹기 한 시간 전의 양을 출력한다.
주의할 점
Q. 남아 있는 치즈를 구하는데 왜 녹는 치즈의 양을 출력하는 걸까?
문제 예시로 보면 ans는 [31, 22, 5, 0]이 나온다.
즉, 한 시간 후에는 31 만큼이, 두 시간 후에는 22 만큼, 세 시간 후에는 5 만큼 녹는 것이다.
이를 다르게 말하면 두 시간 전에는 5만큼 남았다는 뜻이고, 세 시간 전에는 22만큼 남았다는 뜻이 된다.
그래서 이해가 안 되면 빼줘도 되지만
녹는 치즈의 양을 바꿔서 생각하면 그 전 시간에는 남아 있는 치즈가 되는 것이다.
최종 코드
from collections import deque
n, m = map(int, input().split())
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
adjMatrix = []
visited = [[0 for _ in range(m)] for _ in range(n)]
bfsQueue = deque([])
ans = []
for _ in range(n) :
adjMatrix.append(list(map(int, input().split())))
def bfs() :
cnt = 0
while bfsQueue :
currentLocation = bfsQueue.popleft()
curY = currentLocation[0]
curX = currentLocation[1]
for i in range(4) :
ny = curY + dy[i]
nx = curX + dx[i]
if 0 <= ny < n and 0 <= nx < m and visited[ny][nx] == 0 :
if adjMatrix[ny][nx] == 0 :
visited[ny][nx] = 1
bfsQueue.append((ny, nx))
elif adjMatrix[ny][nx] == 1 :
adjMatrix[ny][nx] = 0
visited[ny][nx] = 1
cnt += 1
ans.append(cnt)
return cnt
while True :
visited = [[0 for _ in range(m)] for _ in range(n)]
visited[0][0] = 1
bfsQueue.append([0, 0])
cnt = bfs()
if cnt == 0 :
break
print(len(ans)-1)
print(ans[-2])
I mean