[Python/파이썬] 백준 3055번: 탈출

문제

 

풀이

입력받는 코드

from collections import deque
input = __import__('sys').stdin.readline

r, c = map(int, input().split())
graph = [list(input().strip()) for _ in range(r)]
waterVisited = [[False] * c for _ in range(r)]
dociVisited = [[False] * c for _ in range(r)]
water = deque()
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

 

굴, 고슴도치, 물의 위치를 찾아주었다.

물 같은 경우 bfs를 수행해야 하므로 deque에 넣었다.

# 초기값 설정
for i in range(r):
    for j in range(c):
        if graph[i][j] == 'D':
            cave = (i, j)
        if graph[i][j] == 'S':
            doci = (i, j, 0)
            dociVisited[i][j] = True
        if graph[i][j] == '*':
            water.append((i, j, 0))
            waterVisited[i][j] = True

 

물의 흐름을 처리하는 코드

새로 추가된 물은 다음 시간에 흐르므로 기존에 있던 물의 수만큼만 반복문 수행

def waterFlow():
    for _ in range(len(water)):
        i, j, cnt = water.popleft()
        move(i, j, 0, waterVisited, 'D', 'X', water, True)

 

고슴도치의 이동을 처리하는 코드

prevCnt를 통해 시간이 흘렀을 때만 물이 흐르게 구현 (큐의 특징을 알면 이해하기 쉽다)

def moveDoci():
    q = deque()
    q.append(doci)
    cnt = 0
    prevCnt = -1
    while q:
        i, j, cnt = q.popleft()
        if prevCnt < cnt:
            prevCnt = cnt
            waterFlow()
        if ((i, j) == cave):
            print(cnt)
            return
        move(i, j, cnt, dociVisited, '*', 'X', q, False)
    print("KAKTUS")

 

move 함수

고슴도치와 물의 이동을 동시에 처리한다.

cnt의 경우 고슴도치에만 필요한 변수이고

mark가 True인 경우 해당 위치를 물로 채운다.

def move(i ,j, cnt, visited, s1, s2, que, mark):
    for idx in range(4):
        ni, nj = i + dy[idx], j + dx[idx]
        if check(ni, nj, visited, s1, s2): continue
        que.append((ni, nj, cnt + 1))
        visited[ni][nj] = True
        if mark: graph[ni][nj] = '*'

check 함수

배열이 값을 벗어나지 않았는지 등을 체크하는 함수

def check(ni, nj, visited, s1, s2):
    return ni < 0 or ni >= r or nj < 0 or nj >= c or visited[ni][nj] or graph[ni][nj] == s1 or graph[ni][nj] == s2

 

코드

from collections import deque
input = __import__('sys').stdin.readline

r, c = map(int, input().split())
graph = [list(input().strip()) for _ in range(r)]
waterVisited = [[False] * c for _ in range(r)]
dociVisited = [[False] * c for _ in range(r)]
water = deque()
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

# 초기값 설정
for i in range(r):
    for j in range(c):
        if graph[i][j] == 'D':
            cave = (i, j)
        if graph[i][j] == 'S':
            doci = (i, j, 0)
            dociVisited[i][j] = True
        if graph[i][j] == '*':
            water.append((i, j, 0))
            waterVisited[i][j] = True
      
def waterFlow():
    for _ in range(len(water)):
        i, j, cnt = water.popleft()
        move(i, j, 0, waterVisited, 'D', 'X', water, True)
                   
def check(ni, nj, visited, s1, s2):
    return ni < 0 or ni >= r or nj < 0 or nj >= c or visited[ni][nj] or graph[ni][nj] == s1 or graph[ni][nj] == s2

def moveDoci():
    q = deque()
    q.append(doci)
    cnt = 0
    prevCnt = -1
    while q:
        i, j, cnt = q.popleft()
        if prevCnt < cnt:
            prevCnt = cnt
            waterFlow()
        if ((i, j) == cave):
            print(cnt)
            return
        move(i, j, cnt, dociVisited, '*', 'X', q, False)
    print("KAKTUS")

def move(i ,j, cnt, visited, s1, s2, que, mark):
    for idx in range(4):
        ni, nj = i + dy[idx], j + dx[idx]
        if check(ni, nj, visited, s1, s2): continue
        que.append((ni, nj, cnt + 1))
        visited[ni][nj] = True
        if mark: graph[ni][nj] = '*'
        
moveDoci()

 

마무리

저번에 푼 골드 1 문제보다는 쉬워서 금방 풀었다 ㅎㅎ