소프티어

안녕하세요.

로직을 간단하게 설명드리면

1. 소나기 위치를 저장해줌

2. 처음에 소나기를 이동시킴

3. 이동시킨 소나기의 위치나 강이 아니면 W를 dfs를 이용해 탐색

4. 2,3번 반복

이런 방식입니다.

시간초과가 나고 오답도 있는데 어느 부분에서 시간을 줄일 수 있을지.. 그리고 어느 부분이 틀린건지 피드백 주시면 감사하겠습니다.

import copy

r, c = map(int, input().split())
list_map = [list(map(str, input())) for _ in range(r)]
shower_map = [['0'] * c for _ in range(r)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

ans = int(1e9)
list_shower = [] # 소나기 위치 저장
for i in range(r):
    for j in range(c):
        if list_map[i][j] == '*':
            list_shower.append((i,j))

def shower(): # 소나기 이동하는 부분
    global list_shower
    tmp = []
    for a, b in list_shower:
        for d in range(4):
            nx = a + dx[d]
            ny = b + dy[d]
            if not(0 <= nx < r and 0 <= ny < c):
                continue
            if list_map[nx][ny] == '.':
                tmp.append((nx, ny))
    list_shower += tmp
    list_shower = list(set(list_shower))

visited = [[False] * c for _ in range(r)]

def dfs(cx, cy, num, result):
    global list_map
    global ans
    visited[cx][cy] = True
    if result == 1:
        ans = min(ans, num)
        return
    if list_map[cx][cy] == 'W':
        for d in range(4):
            nx = cx + dx[d]
            ny = cy + dy[d]

            if 0 <= nx < r and 0 <= ny < c and visited[nx][ny] == False:
                if visited[nx][ny] == True:
                    continue
                if list_map[nx][ny] == 'X' or (nx, ny) in list_shower:
                    continue
                if list_map[nx][ny] == 'H':
                    result += 1
                tmp_map = copy.deepcopy(list_map)
                list_map[nx][ny] = 'W'
                list_map[cx][cy] = '.'
                shower()
                dfs(nx, ny, num+1, result)
                list_map = copy.deepcopy(tmp_map)
    visited[cx][cy] = False

for i in range(r):
    for j in range(c):
        if list_map[i][j] == 'W':
            shower()
            dfs(i, j, 0, 0)

if ans == int(1e9):
    ans = 'FAIL'

print(ans)