백준 알고리즘 3055번 탈출 풀이 with Python

문제 링크: https://www.acmicpc.net/problem/3055

3055번: 탈출

문제는 다음과 같다.

문제의 핵심은 각 시간마다 물이 갈 수 있는 곳을 먼저 설정해주고 다음으로 고슴도치를 이동시켜야 한다. 고슴도치를 먼저 이동시키면 그곳에 물이 들어갈 수도 있기 때문이다. 내가 해결한 코드는 다음과 같다.

def solution(start, map1, water, r, c):
    global waterdic
    global visit
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    time = 0
    queue = [[start[0], start[1]]]
    while 1:
        sub = []
        sub2 = []
        for w in water:
            x = w[0]
            y = w[1]
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if -1 < nx < r and -1 < ny < c:
                    if waterdic.get((nx, ny)):
                        continue
                    else:
                        t = map1[nx][ny]
                        if t != 'D' and t != 'X':
                            waterdic[nx, ny] = True
                            sub2.append([nx, ny])
        water = sub2
        for p in queue:
            x = p[0]
            y = p[1]
            if map1[x][y] == 'D':
                return time
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if -1 < nx < r and -1 < ny < c:
                    if waterdic.get((nx, ny)) or visit.get((nx, ny)) or map1[nx][ny] == 'X':
                        continue
                    else:
                        visit[(nx, ny)] = True
                        sub.append([nx, ny])
        queue = sub
        time += 1
        if not queue:
            break
    return -1


r, c = map(int, input().split())
map1 = []
start = []
water1 = []
waterdic = {}
visit = {}
for i in range(r):
    s = input()
    for j in range(c):
        if s[j] == 'S':
            start = [i, j]
        elif s[j] == '*':
            water1.append([i, j])
    map1.append(s)
ans = solution(start,map1,water1,r,c)
if ans == -1:
    print('KAKTUS')
else:
    print(ans)