[백준] 3055번: 탈출 (python)

www.acmicpc.net/problem/3055

3055번: 탈출

import sys

def find_loc(R,C,chart,e='S'):
    loc = []
    for r in range(R):
        for c in range(C):
            if chart[r][c] == e:
                loc.append([r,c])
    return loc
    
def move_position(R,C,chart,s_loc):
    expand = []
    goal = False
    for l in s_loc:
        lr,lc = l
        near = [[lr,lc+1],
                [lr+1,lc],
                [lr,lc-1],
                [lr-1,lc]]
        for n in near:
            nr,nc = n
            if nr >-1 and nr < R:
                if nc > -1 and nc < C:
                    if chart[nr][nc] == '.':
                        chart[nr][nc] = 'S'
                        expand.append(n)
                    elif chart[nr][nc] == 'D':
                        goal = True
                        expand.append(n)
    return chart, expand, goal

def expand_water(R,C,chart,water_loc):
    expand = []
    for l in water_loc:
        lr,lc = l
        near = [[lr,lc+1],
                [lr+1,lc],
                [lr,lc-1],
                [lr-1,lc]]
        for n in near:
            nr,nc = n
            if nr >-1 and nr < R:
                if nc > -1 and nc < C:
                    if chart[nr][nc] == '.' or chart[nr][nc] == 'S':
                        chart[nr][nc] = '*'
                        expand.append(n)
    return chart, expand

if __name__ == '__main__':

    R, C = list(map(int,input().split()))
    chart = [list(map(str,sys.stdin.readline())) for _ in range(R)]

    num_move = 0
    goal = False

    s_loc = find_loc(R,C,chart,e='S')
    w_loc = find_loc(R,C,chart,e='*')

    while(True):

        chart, w_loc = expand_water(R,C,chart,w_loc)
        chart, s_loc, goal = move_position(R,C,chart,s_loc)

        num_move += 1
        
        if goal:
            print(num_move)
            break
        elif not s_loc:
            print('KAKTUS')
            break