[baekjoon] 백준 3055번(파이썬): 탈출

문제

3055번: 탈출

알고리즘

- bfs 탐색을 통해 문제를 수행한다.

- 반복문을 통해 시작점의 위치와 물의 위치를 리스트에 담는다.

- 고슴도치가 이동할 수 있는 곳과 물이 잠길 수 있는 곳을 bfs 탐색을 한다.

- bfs 탐색을 할 때 주의해야 할 점은 임시 리스트를 하나 만들어 현재 탐색해야 하는 곳과 다음에 탐색해야 하는 곳을 나눠 탐색해야 한다는 것이다. (고슴도치의 이동과 물이 잠기는 것은 현재!! 기준으로 수행해야 하기 때문.)

- 물이 잠겼다면 고슴도치가 이동할 수 없는 것을 상기시키면서 알고리즘을 짜야한다.

- 고슴도치가 비버의 굴로 이동했다면 비버의 굴까지 이동한 횟수를 리턴한다.

- 고슴도치가 이동할 수 있는 모든 곳을 이동했지만 비버의 굴에 도달하지 못했다면 "KAKTUS"를 리턴한다.

코드

import sys
from collections import deque


# 물이 차있는 지역 bfs 탐색
def _water():
    global water
    temp_water = [] # 물이 차 있는 지역

    # 물이 차있는 모든 지역을 탐색
    while water:
        x, y = water.popleft()

        # 상/하/좌/우 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위 내에 있고
            if 0 <= nx < r and 0 <= ny < c:
                # 이동할 수 있는 곳이라면 물이 차게된다.
                if graph[nx][ny] == ".":
                    graph[nx][ny] = "*"
                    visited[nx][ny] = -1
                    temp_water.append([nx, ny]) # 물이 찬 지역을 임시 큐에 저장

    # 물이 찰 수 있는 지역이 물로 다 채워졌다면
    # 임시 큐에 있는 다음 탐색할 곳을 큐에 추가
    for a, b in temp_water:
        water.append([a, b])


# 고슴도치의 이동 bfs 탐색
def bfs():
    global queue

    while queue:
        temp_queue = [] # 임시 큐

        # 고슴도치가 이동할 수 있는 모든 곳을 탐색
        while queue:

            x, y = queue.popleft()

            # 물이 아니고 돌이 아니라면
            if graph[x][y] != "*" and graph[x][y] != "X":

                # 상/하/좌/우 탐색
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]

                    # 탐색하는 곳이 범위 내에 있다면
                    if 0 <= nx < r and 0 <= ny < c:

                        # 비버의 굴이라면 비버의 굴까지 걸리는 이동 횟수 리턴
                        if graph[nx][ny] == "D":
                            return visited[x][y] + 1

                        # 비어 있는 곳이고 탐색하지 않은 곳이라면 탐색
                        elif graph[nx][ny] == "." and visited[nx][ny] == 0:
                            visited[nx][ny] = visited[x][y] + 1 # 탐색하기까지 걸린 이동 횟수 초기화
                            temp_queue.append([nx, ny]) # 임시 큐에 탐색할 곳을 추가

        # 고슴도치가 현재 이동할 수 있는 곳을 모두 이동했다면
        # 임시 큐에 있는 다음 탐색할 곳을 큐에 추가
        for a, b in temp_queue:
            queue.append([a, b])

        # 물이 차있는 지역 증가
        _water()

    # 고슴도치가 목적지까지 이동할 수 없다면 "KAKTUS" 리턴
    return "KAKTUS"


r, c = map(int, sys.stdin.readline().split())

graph = [list(map(str, sys.stdin.readline().strip())) for _ in range(r)]
visited = [[0 for _ in range(c)] for _ in range(r)] # 이동 횟수, 탐색여부

queue = deque([])
water = deque([])

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

# 그래프를 탐색해 고슴도치의 위치와 물의 위치를 찾는다.
for i in range(r):
    for j in range(c):
        if graph[i][j] == "S":
            queue.append([i, j])

        elif graph[i][j] == "*":
            water.append([i, j])

# bfs 탐색
print(bfs())

 

실패한 코드(21%.. 틀렸습니다.)

import sys
from collections import deque


# 21% 실패
def _water():
    global water
    water_plus = []

    while water:
        x, y = water.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < r and 0 <= ny < c:
                if graph[nx][ny] == ".":
                    graph[nx][ny] = "*"
                    visited[nx][ny] = -1
                    water_plus.append([nx, ny])

    for a, b in water_plus:
        water.append([a, b])


def bfs():
    global queue

    while queue:
        queue_plus = []
        while queue:

            x, y = queue.popleft()
            
            #############여기###############

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if 0 <= nx < r and 0 <= ny < c:
                    if graph[nx][ny] == "D":
                        return visited[x][y] + 1

                    elif graph[nx][ny] == "." and visited[nx][ny] == 0:
                        visited[nx][ny] = visited[x][y] + 1
                        queue_plus.append([nx, ny])

        for a, b in queue_plus:
            queue.append([a, b])

        _water()

    return "KAKTUS"


r, c = map(int, sys.stdin.readline().split())

graph = [list(map(str, sys.stdin.readline().strip())) for _ in range(r)]
visited = [[0 for _ in range(c)] for _ in range(r)]

queue = deque([])
water = deque([])

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

for i in range(r):
    for j in range(c):
        if graph[i][j] == "S":
            queue.append([i, j])

        elif graph[i][j] == "*":
            water.append([i, j])

print(bfs())

코드를 보게 되면 성공한 코드와 한 줄 빼고 다 똑같은걸 확인할 수 있다.

물이 증가하면서 고슴도치가 이동할 수 있는 곳이 물에 잠기게 되는데, 그걸 생각하지 않고 문제를 수행했기 때문에 틀렸다는 결과가 나온 것이다. 코드의 흐름을 끝까지 확인하지 않고 부분별로 확인했기에 이런 아쉬운 결과가 나온 것 같다. 다음에는 끝까지 코드의 흐름을 확인해서 시간 낭비를 하지 말아야겠다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법