벽 부수고 이동하기

백준 2206 파이썬 풀이 (BFS, 벽 부수고 이동하기, 이차 배열 사용)

이 문제는 정말 나를 못살게 괴롭히는 놈이었다. 배열을 어떻게 해야할지 어떤 기준으로 visited를 하게 할지 굉장히 고민을 많이 하게 만들었다. 3차원 배열로 풀으라는데 내 방식대로 풀기 위해 상당히 고생을 했다. 우선 경우를 나누어본다. 벽을 뿌수고 이동하는 경우에는 다양하게 길이 갈리게 된다. 따라서 이미 누군가 지나간 길에 대해서 계속 갈지 말지를 정해야한다. 편의상 플레이어(경로를 가는 포인트)와 스킬(벽을 부쉈는지 아닌지)이라고 하겠다. 그렇다면 4가지 경우로 나눈다. 1. 스킬을 쓰지 않은 플레이어가 지나간 자리를 스킬을 쓰지 않은 플레이어가 마주쳤을때 => 더이상 진행할 이유가 없다. 왜냐면 앞선 플레이어가 더 효율적 2. 스킬을 쓰지 않은 플레이어가 지나간 자리를 스킬을 쓴 플레이어가 ..