이전에 풀었었던 그림 문제와 유사한 문제로 미로 탐색 문제를 풀어보았습니다. 미로 탐색 문제도 BFS알고리즘의 기본적인 문제였습니다. 문제를 풀어보면서 느꼈지만 이전에 알고리즘 공부를 하셨던 분들이거나 BFS & DFS를 알지만 까먹으신 분들에게는 복습하기에 좋은 문제라고 생각이 듭니다.
문제 주소 : https://www.acmicpc.net/problem/2178
이 문제의 경우 제가 평소에 코딩테스트 공부를 하면서 즐겨듣는 유튜브 강의영상 중 https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3
나동빈의 이코테 강의 중 BFS & DFS강좌의 문제풀이에 나온 문제와 풀이가 비슷했습니다.
바로 코드리뷰 시작해보겠습니다!!
전체코드입니다.
위에서부터 리뷰를 시작해보자면 우선 BFS알고리즘은 queue 자료구조를 사용하여 문제풀이를 하는게 문제해결에 좋기 때문에 queue 자료구조를 사용해야합니다!
queue를 사용하기 위해서는 deque 라이브러리를 사용해야하기 때문에 제일 먼저 deque 라이브러리를 import해주었습니다. 그 다음 그래프를 초기화 해주고, 행과 열을 입력받고, 공백을 기준으로 구분하여 입력을 받기위한 코드를 작성해주었습니다.
다음으로는 BFS함수를 선언하기 전에 상하좌우 좌표설정을 해주었습니다!
BFS함수부분은 우선 BFS를 선언해주고, queue에 deque 을 선언해줍니다!
*주의 : queue.append안에 있는 x,y는 한 묶음 이기 때문에 따로 따로 묶어주면 큰일납니다!!!
이후에 while반복문을 통해서 queue에 값이 없을 때까지 반복문을 동작시킵니다! 먼저 queue에 들어온 값을 시~원하게 제거한 후 x와 y에 값을 저장해준 다음, for 문을 돌려서 dx,dy를 통해 상하좌우의 값을 확인해 봅니다.
확인을 하면서 몇가지의 예외처리를 해줘야 하는데
첫 째! : 미로 속 칸의 범위가 미로의 범위를 벗어나는경우.
둘 째! : 미로 속 칸이 벽에 닿았을 때!
이 두 경우를 예외처리를 해줘야하는데 처리코드는 다음과 같습니다.
이런식으로 if문을 사용하여서 예외처리를 해주시면 됩니다!
이제 정상적으로 이동이 가능한 경우를 처리해주면 되는데, 값이 잘 이동하였다면 그 값을 확인해줍니다.
if문을 사용하여 이동한 칸에 1이 써있다면? 이동이 가능!
그렇다면 이전에 있었던 x,y좌표에 1을 더해서 저장을 해주고, 이제 이동한 nx,ny칸으로 이동을 해줍니다.
마지막으로 리턴을 해주면 되는데
이렇게 행열의 시작은 0부터 시작카운트를 세기 시작했기 때문에 리턴 값에는 -1을 해준 결과를 리턴해줍니다!
리턴이 끝났다면 이제 print문으로 결과값을 출력만 해주면 문제가 끝이납니다!
위와 같이 잘 따라하셨다면 아마 결과는 이렇게 잘 나오셨을 겁니다!
결과도 잘 나오셨다면 아주 잘 하신겁니다!!!
백준사이트에서도 문제없이 잘 나오네요ㅎㅎㅎ
감사합니다!!
