Softeer Level 3 GINI야 도와줘 Python

문제 링크

https://softeer.ai/practice/6271

Softeer - 현대자동차그룹 SW인재확보플랫폼

정답 코드

import sys
from collections import deque

input = sys.stdin.readline

R, C = map(int, input().split())

guidance = []
shower = []
boundaryShower = []
sr, sc = 0, 0
er, ec = 0, 0

def isValid(nr, nc):
    return 0 <= nr < R and 0 <= nc < C

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

for r in range(R):
    line = input().strip()
    for c in range(C):
        tmp = line[c]
        if tmp == "H":
            er, ec = r, c
        elif tmp == "W":
            sr, sc = r, c
        elif tmp == "*":
            shower.append((r, c))   
    guidance.append(line)

V = [[0 for _ in range(C)] for _ in range(R)]

for shR, shC in shower:
    isBoundary = False
    for d in range(4):
        nr = shR + dr[d]
        nc = shC + dc[d]
        if isValid(nr, nc) and guidance[nr][nc] == ".":
            isBoundary = True
            break
    if isBoundary:
        boundaryShower.append((shR, shC))

showerQ = deque(boundaryShower)
taebeomQ = deque([(sr, sc)])
time = 1

tabeomIsHome = False
while taebeomQ:
    # 태범이 집에 있으면 중단
    if tabeomIsHome:
        break
    # 소나기 출발
    while showerQ:
        r, c = showerQ.popleft()
        if V[r][c] == time + 1:
            showerQ.append((r, c))
            break
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if isValid(nr, nc) and guidance[nr][nc] == "." and not V[nr][nc]:
                showerQ.append((nr, nc))
                V[nr][nc] = V[r][c] + 1

    # 태범이 출발
    while taebeomQ:
        r, c = taebeomQ.popleft()
        if V[r][c] == time + 1:
            taebeomQ.append((r, c))
            break
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if isValid(nr, nc):
                if not V[nr][nc]:
                    if guidance[nr][nc] == ".":
                        V[nr][nc] = V[r][c] + 1
                        taebeomQ.append((nr, nc))
                    elif guidance[nr][nc] == "H":
                        V[nr][nc] = V[r][c] + 1
                        tabeomIsHome = True
                        break
    time += 1
endTime = V[er][ec]
if endTime:
    print(V[er][ec])
else:
    print("FAIL")

풀이 방법

1. 태범이 집의 위치와 세차장 위치 그리고 소나기의 위치를 저장한다.
2. 사실 이것도 소나기가 하나인지 모르니까 일단 deque에 저장한다.
3. 저장한 소나기 중에 "."에 인접한 소나기만 다시 저장한다.
4. 시간이 지나면서 소나기 확산시키고 그 뒤에 태범이를 확산?시킨다.
5. 방문배열을 공유해도 되는 이유는 어차피 방문배열의 값이 존재하면 태범이도 이동 못하기 때문이다.
6. 맨 처음 while문에 태범이의 q가 비어있으면 어차피 태범이는 집을 못 가므로 중단시킨다.
7. 마지막으로 방문배열의 태범이 집 값이 곧 걸린 시간이므로 출력한다.
   1. 시간이 0이면 FAIL을 출력한다.

느낀점

• 백준의 얼음 녹는 문제가 떠올랐다.
  • 얼음이 1시간마다 녹았고 얼마나 걸려야 다 녹는 문제
  • 다른 문제는 너무 오래되서 기억은 안나는데 이동하는 문제였다.
• 차근차근히 읽고 풀면 되는 문제지만 처음 떠올리는게 생각보다 오래걸려서 많이 풀어봐야 겠다는 생각이 들었다.