백준 2206: 벽 부수고 이동하기 (Swift)

typealias Point를 3개의 Int를 가진 튜플 형태로 만들어 (x좌표, y좌표, 벽을 부순적 있는지 여부 0/1 ) 를 나타내도록 하였다.

 

어떤 칸 a, b에 

1. 10개의 칸을 지나며 벽을 1번 부수고 도착한 경우

2. 20개의 칸을 지나며  벽을 0번 부수고 도착한 경우

 

두가지 경우가 있다고 생각해보자

bfs로 진행하므로, 1번 경우를 우리는 queue에서 먼저 꺼내게 될 것이다.

우리가 visited라는 2차원 배열에 각 칸을 지난적 있는지 여부를 표시해왔다고 가정해보자.

2번 경우를 뽑았을 때, 이미 visited[a][b] == true 로 표시되어있을 것이다.

--> 그렇다면 우리는 2번 경우를 무시해도 되는 것일까?

 

절대 안된다.

 

a,b 칸에서 벽을 하나 더 뚫을 경우 10번만에 도착점까지 갈 수 있지만, 벽을 더 뚫지 못하는 경우 빙~ 돌아 40번만에야 도착할 수 있는 경우가 있을 수 있기 때문이다.

 

+ 우리는 현재 진행 상황에서 벽을 뚫은 적 있는지 없는지를 항상 체크해야한다.

따라서 typealias Point를 queue에 넣고 빼며 마지막 Int가 0이면 벽을 뚫은 적 없는 것, 1이면 벽을 뚫은 적 있는 것 

이를 고려하여 bfs를 진행하였다.