기상캐스터 - 실버5 (백준, 구현)

import sys

def find(y,x):
  maps[y][x] = 0
  stack = []
  stack.append(x)
  while stack:
    dx = stack.pop()
    if dx + 1 < W and sky[y][dx+1] == '.':
      maps[y][dx+1] = maps[y][dx]+1
      stack.append(dx+1)
    elif dx + 1 < W and sky[y][dx+1] == 'c':
      maps[y][dx+1] = 0
      stack.append(dx+1)

input = sys.stdin.readline
H, W = map(int,input().split())

sky = [list(input()) for _ in range(H)]
maps = [[-1]*W for _ in range(H)]

for i in range(H):
  for j in range(W):
    if sky[i][j] == 'c':
      find(i,j)
  print(' '.join(map(str,maps[i])))

 bfs로도 풀 수 있지만 어차피 한 줄을 한 번씩만 탐색하면 되는 문제라서 stack에 담아서 값을 조회하는 식으로 풀었다.

 

이거 보다 더 빠르고 쉽게 푸는 방법은

import sys

input = sys.stdin.readline
H, W = map(int,input().split())

sky = [list(input()) for _ in range(H)]
maps = [[-1]*W for _ in range(H)]

for i in range(H):
  sig = -1
  for j in range(W):
    if sky[i][j] == 'c':
      print(0, end=' ')
      sig = j
    elif sig > -1:
      print(j-sig, end=' ')
    else:
      print(-1, end=' ')
  print()

위의 코드와 같다. 그냥 sig를 하나 만들고 c일때는 0으로 sig를 j로 초기화한다.

 

이후 만약 sig가 변경됨을 감지하면 j에서 sig만큼을 빼주고

 

모든 예외사항은 -1을 출력한다.

 

44ms가 두번째 코드이다.