[DFS, BFS] 백준 3055번: 탈출 / 골드 5

https://www.acmicpc.net/problem/3055

3055번: 탈출

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제

www.acmicpc.net

import collections
x_lim, y_lim = map(int, input().split())

graph = []
visit = []
start = []
target = []
for x in range(x_lim):
    row = [x for x in input()]
    graph.append(row)
    visit.append([False]*len(row))
    for y in range(len(row)):
        if row[y] == 'D':
            target = [x, y]
        if row[y] == 'S':
            start = [x, y]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

q = collections.deque()
q.append([0, start[0], start[1]])  # time, x, y
while q:
    for _ in range(len(q)):
        time, x, y = q.popleft()
        if not visit[x][y] and graph[x][y] != '*':
            visit[x][y] = True
            if [x, y] == target:  # finish
                print(time)
                quit()

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < x_lim and 0 <= ny < y_lim and not visit[nx][ny]:
                    if graph[nx][ny] not in "X*":  # possible
                        q.append([time + 1, nx, ny])

    # water spread
    for x in range(x_lim):
        for y in range(y_lim):
            if graph[x][y] == "*":
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0 <= nx < x_lim and 0 <= ny < y_lim:
                        if graph[nx][ny] == ".":
                            graph[nx][ny] = "#"

    for x in range(x_lim):
        for y in range(y_lim):
            if graph[x][y] == "#":
                graph[x][y] = "*"

print("KAKTUS")