[백준 Gold IV] 알고스팟 - 1261 (python)

문제 설명

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.

(1, 1)과 (N, M)은 항상 뚫려있다.

출력

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

 

예제 입력 1 

3 3
011
111
110

예제 출력 1 

3

예제 입력 2 

4 2
0001
1000

예제 출력 2 

0

 

 

 

 

---

 

첫번째 시도 (메모리 초과)

from collections import deque

N, M = map(int, input().split())
graph = [] # 미로의 벽 정보 저장하는 리스트

for i in range(M):
    graph.append(list(map(int, input())))

count = [[-1] * N for _ in range(M)] # 벽을 부순 횟수 리스트

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

def BFS(a, b):
    q = deque()
    q.append([a, b]) # 초기 상태 (0, 0)을 넣는다
    count[0][0] = 0 # 이동 전 초기 상태

    while q:
        x, y = q.popleft() # 큐에 있는 값을 왼쪽부터 빼기
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # map을 벗어나는 경우
            if nx < 0 or nx >= M or ny < 0 or ny >= M:
                continue

            if count[ny][ny] == -1:
                # 빈 방인 경우
                if graph[nx][ny] == 0:
                    count[nx][ny] = count[x][y] # count 변화 없음
                    q.appendleft([nx, ny]) # 벽이 없는 곳으로 우선 가기 (큐의 왼쪽에 추가)
                else:
                    # 벽이 있는 경우
                    count[ny][ny] = count[x][y] + 1 # count + 1
                    q.append([nx, ny]) # 큐의 맨 오른쪽에 추가

BFS(0, 0)
print(count[M-1][N-1])

 

1. (1,1) 에서 (N, M)을 이동하는 경우의 수 모두 구하기
=> 벽을 깬 횟수를 저장하는 리스트 만들기(count)
- 상하좌우로만 이동 가능
- 0 > 0 : 0
- 0 > 1 : 1
- 1 > 1 : 1
- 1 > 0 : 0

2. 경우의 수 중 answer이 가장 작은 경우 구하기
=> 0을 우선으로 돌아야 한다 => 큐에 추가할때 appendLeft로 추가해주어야 한다

 

위의 순서를 메모장에 적어두고 1시간 정도 걸려서 풀었는데,

 

메모리 초과가 나왔다.

 

구글링해서 원인을 찾아보다가,

BFS 같은 알고리즘을 사용할 때 재귀적 호출을 통해 너무 많은 함수를 호출할 경우에 메모리 초과가 나온다고 한다.

아무래도 BFS 함수를 생성해서 사용한 게 원인이 아닐까 싶다.

 

 

 

 

두번째 시도 (정답)

from collections import deque

m, n = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
count = [[-1] * m for _ in range(n)]

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

q = deque()
q.append((0, 0))
count[0][0] = 0

while q:
    x, y = q.popleft()

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

        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue

        if count[nx][ny] == -1:
            if graph[nx][ny] == 0:
                count[nx][ny] = count[x][y]
                q.appendleft((nx, ny))
            elif graph[nx][ny] == 1:
                count[nx][ny] = count[x][y] + 1
                q.append((nx, ny))

print(count[n-1][m-1])

 

그래서 함수를 빼고,

while 문으로만 생성해서 하니 정답...!

 

 

이번에, appendleft를 새로 알게 되었다.

append(x)가 오른쪽에서 추가(삽입)을 해준다면, appendleft(x)는 왼쪽 즉, 앞쪽에서 리스트를 추가(삽입)해주는 메소드이다.

0인 경우부터 우선으로 돌아가야 하기 때문에 appendleft를 통해 더 빠르게 접근할 수 있도록 하는 것이었다.

그냥 append를 쓰면 시간 초과가 나더라.

이건 따로 정리할 예정이다.

 

 

확실히 알고리즘 유형대로 푸니까 조금 알것 같기는 하다. 문제는, 그냥 문제를 보면 어떤 유형인지 아직 잘 모르겠다는 것...좀 더 열심히 공부해야겠다.