JOI시는 남북방향이 H 킬로미터, 동서방향이 W 킬로미터인 직사각형 모양이다. JOI시는 가로와 세로의 길이가 1킬로미터인 H × W 개의 작은 구역들로 나뉘어 있다. 북쪽으로부터 i 번째, 서쪽으로부터 j 번째에 있는 구역을 (i, j) 로 표시한다.
각 구역의 하늘에는 구름이 있을 수도, 없을 수도 있다. 모든 구름은 1분이 지날 때마다 1킬로미터씩 동쪽으로 이동한다. 오늘은 날씨가 정말 좋기 때문에 JOI시의 외부에서 구름이 이동해 오는 경우는 없다.
지금 각 구역의 하늘에 구름이 있는지 없는지를 알고 있다. 기상청에서 일하고 있는 여러분은 각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 예측하는 일을 맡았다.
각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 구하여라.
이 문제는 탐색을 활용하여 풀었다. 다만 기존에 탐색에서 상,하,좌,우로 이동을 했다면 이 문제에선 오른쪽으로만 움직이는것에 해당되니, 오른쪽으로만 진행하는 로직으로 짜봤다.
📃 소스코드 및 설명
from collections import deque
N, M = map(int,input().split())
# 시작은 모두 지점에 구름이 없는 경우 즉, -1로 시작한다.
visited = [[-1] * M for _ in range(N)]
# N줄 만큼 입력
graph = [list(map(str, input())) for _ in range(N)]
def bfs(x, y):
count = 0
queue = deque()
queue.append([x, y])
while queue:
x, y = queue.popleft()
#오른쪽으로만 이동할 예정이기에 y만 증가시켜주면서 진행한다.
nx = x
ny = y + 1
# 범위안에 있는가?
if 0<=nx<N and 0<=ny<M:
# 범위 안에 있고,
# 다음 지점이 구름이 없는 경우
# 다음 지점이 아직 방문을 안했을 경우
# 현재 지점이 0보다 클때(구름이 있고 다음 지점은 구름이 이동할 지점이여야 하니)
# 누적된 값이 들어올때도 조건문 안으로 들어갈 수 있도록 처리해준다.
# 위의 조건식이 다 통과되었을 경우! 누적된 값을 visited 배열에 넣어준다.
if visited[x][y] >= 0 and visited[nx][ny] == -1 and graph[nx][ny] == '.' :
count += 1
visited[nx][ny] = count
queue.append([nx, ny])
# 열
for x in range(N):
# # 행
for y in range(M):
# 입력된 값에서 c가 있는 좌표가 있으면 그때 구름의 유무를 0으로 바꿔준다.
if graph[x][y] == 'c':
visited[x][y] = 0
bfs(x, y)
# print(graph)
for i in visited:
print(*i)
