[백준] 1261 알고스팟 (파이썬), 다양한 방법

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

1261번: 알고스팟

bfs/dfs를 이용한 그래프 순회 문제임은 쉽게 알 수 있다. 문제는 '목표 지점에 도착하기 위해 벽을 뚫어야 하는 최소 갯수'를 어떻게 구하느냐이다.

 

풀이 및 정답 코드

방법 1. 파이썬 기준 52ms

#9328(https://www.acmicpc.net/problem/9328, 골드1)과 비슷하다. dfs, bfs 도중 마주친 벽을 별도의 deque/stack에 저장하고 그래프 순회가 끝났다면 broken_wall_cnt를 1 증가시킨 뒤 별도의 자료에서 다시 순회한다. 

stack, new_stack = [(0, 0)], []
for broken_wall_cnt in range(0, C*R+1):
    dfs()
    if visited[R-1][C-1]:
        break
    else:
        stack, new_stack = new_stack, []

print(broken_wall_cnt)

 

방법 2. 파이썬 기준 80ms

0-1 bfs. 벽이 없는 것을 0, 벽이 있는 것을 1 취급한다면 0개 부순 상태, 1개 부순 상태, ~~~ 순서로 그래프를 방문하게 된다.

생략

 

방법 3. 파이썬 기준 64ms

다익스트라. 벽이 없는 것을 0, 벽이 있는 것을 1 취급한다.

생략

 

잘 생각해보면 사실 방법 1과 방법 2는 동일하다는 걸 알 수 있다.

0000000/1111/222

deque/stack에 들어가는 cnt가 위와 같을 경우 방법 1은 슬래시마다 함수를 다시 호출하고 방법 2는 한 번의 함수내에서 deque를 처리한다.

방법 3(다익스트라)는 일반적으로 방법 2(0-1bfs)보다 느리다. 이번 경우에는 오히려 빨랐지만 가급적 효율적인 알고리즘을 선택하도록 하자.

 

소감

풀이 자체는 쉽게 할 수 있었지만 발상이 어려운 문제였다.