2178번 미로 탐색(BFS) - ☆

#문제링크 : https://www.acmicpc.net/problem/2178

<1st try>

큐에 푸쉬가 있으면 다음 뎁스로 넘어가는 것으로 생각할 수 있고, 그 말은 거리가 하나 증가한다는 뜻이다. 그래서 큐에 푸쉬가 있을때 flag변수를 true로 해주고, flag가 true일때, dis를 하나 증가시키는 논리로 코드를 구현했다. 하지만 논리에 오류가 있었다.

1. Code

<2nd try>

푸쉬가 존재할때마다 dis값이 증가하면 같은 뎁스에 있는 노드에서 각기 다른 푸쉬가 존재할때 각각 푸쉬된 노드들은 다른 dis를 가지게 된다. 예를 들어, 2 - (3, 4) 이고 3 - 5 / 4 - (6, 7)이라면 3, 4에서 dis = 1, 3에서 5 푸쉬가 있으므로 5에서 dis = 2, 4에서 6, 7 푸쉬가 있으므로 6과 7에서 dis=3 이 된다. 여기서 5, 6, 7은 같은 뎁스라 dis가 같아야 하지만 다르게 나온다. 결국, 이전 check[x][y]에서 값을 하나 증가시켜야 저런 오류가 생기지 않는다.

2. Code