백준/ Silver 1문제 , 백준 파이썬 2178 , 미로 탐색

백준/ Silver 1문제 , 백준 파이썬 2178 , 미로 탐색

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
어려운 만큼 반복적으로 코드작성을 해보면서 완벽히 익힌 코드이다. 다른 문제를 풀때도 적용해 보겠다.

 

 

<문제 출처>

 

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

2178번: 미로 탐색

------------------------------------------------------------------------------------------------------------------------------

 

 

 

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3 

 

 

이코테 BFS 마지막 미로 문제랑 코드가 같다.

 

코드가 이해가 잘안간다면 영상을 참고해보자.  (52:32 부터 시청하면된다.)

 

 

------------------------------------------------------------------------------------------------------------------------------

 

 

 

코드를 하나하나 살펴 보자.

 

 

우선적으로 작성할 코드이다.

 

N, M 은 행과 열의 입력 값을 받고

 

graph 리스트를 만들어 준 뒤, 이 리스트 안에 주어진 미로를 한 행 씩 집어 넣는다.

 

101111
101010
101011
111011

 

예제 1번을 기준으로 총 4개의 행이 집어 넣어진다.

 

 

다음 으로 작성해야 할 것이 이제 bfs 함수이다.

 

선언 전에 

 

 

deque 라이브러리를 사용할 것이므로 import 해준다.

 

 

 

 

우리는 너비우선탐색을 사용할 것이므로 bfs 를 선언한다.

 

이후 queue 에 deque를 선언한다.

 

참고로 append 내의 x, y는 2개의 원소를 넣는 것이 아닌 (x, y) 한 집합을 넣어주는 것이기때문에

소괄호를 반드시 2번 사용한다.

 

 

 

 

이후 while queue 를 통해 queue 가 빈값이 나올때까지 반복문을 돌린다.

 

queue 에 넣어진 왼쪽값을 pop 시켜 제거 한뒤 x, y 에 저장하고 

 

for 문을 돌려 dx,dy 를 이용하여 상, 하, 좌, 우의 값을 확인한다.

 

그래서 총 4방향을 확인해야 하므로 for i in range(4) 까지 돌리는 것이다.

 

그렇게 나온 각 4개의 nx, ny 를 바로 사용하지 않고 확인 작업을 거쳐야 한다.

 

 

1. 칸이 미로의 벽에 닿는지

 

2. 칸이 미로의 벽을 넘어가는지

 

이 두가지의 경우들에 속하면 값을 받지말고 걸러줘야한다.

 

 

 

 

 

 

이렇게 두개의 if 문을 거쳐서 해당 내용이 없는지 확인 시킨다.

 

 

값이 잘 걸러졌다면 넘겨진 값을 이제 확인한다.

 

 

 

 

만약 넘겨진 칸에 1이 써져있다면 그 칸으로 이동 가능하다.

 

그전의 x, y 칸의 값에 1을 더해준 숫자를 그곳에 부여하고 nx, ny 칸으로 이동한다.

 

이후 queue 에 지금 위치한 nx, ny 값을 전달해 위치를 옮겼다는 것을 알려준다.

 

 

 

while 문을 다돌아 queue 가 빈상태일 경우 최종 목적지까지 도달한 것이다.

 

그 최종 목적지에 있는 값은 몇번만에 이 자리에 도착했는지 값이 매겨져 있을것이기에 

 

그 값을 return 한다.

 

N-1, M-1 을 하는 이유는 행, 열은 0부터 시작해서 셋기때문이다. (자릿수 맞추기 위함)

 

 

 

 

이러한 bfs 함수를 사용하기위해 초기시작지점을 넣어준채 print 하면 코드 작성 완료이다.

 

 

 

 

 

 

 

DFS, BFS 를 처음 접했다면 한번에 이해하기 어려우니 이렇게 코드를 순서대로 따라가보며 코드 리뷰를 해보자.

 

확실히 이해가 잘간다.

 

 

 

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

 

정답