Softeer GINI야 도와줘 (난이도 3)

정답 코드

import sys
r, c = map(int, input().split())

maps = []
for i in range(r):
    maps.append(list(input())) 
v = [[False for i in range(c)] for j in range(r)]
rain = [[False for i in range(c)] for j in range(r)]

def bfs(ro, co):
    tempq = [[] for i in range(2500)]
    cnt = 0
    tempq[0] = [[ro, co]]
    v[ro][co] = True
    pr = [0, 0, 1, -1]
    pc = [1, -1, 0, 0]
    while(len(tempq[cnt])):
        while(len(tempq[cnt])):
            curr = tempq[cnt][0]
            del tempq[cnt][0]
            for i in range(4):
                nr = curr[0] + pr[i]
                nc = curr[1] + pc[i]
                if 0 <= nr < r and 0 <= nc < c and not v[nr][nc] and (maps[nr][nc] == '.' or maps[nr][nc] == 'H'):
                    if maps[nr][nc] == 'H':
                        print(cnt + 1)
                        exit(0)
                    v[nr][nc] = True
                    tempq[cnt + 1].append([nr, nc])
        
        temp = []
        for i in range(r):
            for j in range(c):
                if maps[i][j] == '*':
                    for k in range(4):
                        nr = i + pr[k]
                        nc = j + pc[k]
                        if 0 <= nr < r and 0 <= nc < c and maps[nr][nc] == '.':
                            temp.append([nr, nc])
                            if [nr, nc] in tempq[cnt + 1]:
                                tempq[cnt + 1].remove([nr, nc])
        for t in temp:
            maps[t[0]][t[1]] = '*'
        cnt += 1


for i in range(r):
    for j in range(c):
        if maps[i][j] == 'W':
            bfs(i, j)

print('FAIL')

알고리즘 유형

DFS

후기

더 짧게 작성할 수 있을 것 같다. 다시 풀어야겠다.