[SWEA] D4 : 길찾기 Python

SWEA D4문제를 추천순으로 풀고 있는데 어제오늘은 좀 쉬운 문제를 풀게 됐다. (사실 요즘 바빠서 알고리즘 풀 수 있을까? 했는데 다행이다.)

이 문제는 제목이 길찾기이지만, 사실 미로 찾기, 그래프 탐색하라는 문제이다. 제한시간도 30초이고 최대 방문지 점도 100개이기 때문에 BFS로 풀지, DFS 풀지 고민 없이 풀고 싶은 방식으로 풀어도 해결할 수 있을 것이다.

나는 처음보자마자 BFS가 떠올랐기 때문에, BFS로 풀어보았다.
우선 100개의 방문 체크를 할 리스트를 만들고 인접 행렬을 만들었다.

이 문제는 "출발 도착 출발 도착 출발 도착..." 이런식으로 Input값을 주기 때문에 한 번에 다 받은 다음에 두 개씩 끊어서 인접 행렬에 넣어 줄 필요가 있었다.

변수를 받고 도착지(99)에 도착하면 값을 반환하는 조건을 넣고 BFS를 돌렸는데 코드는 이렇게 된다.

 

교수님께서 이정도 BFS는 3분 안에 구현까지 다하는 속도가 되도록 연습하라고 말씀하셨는데, 난 아직 그 정도 수준은 안되는 것 같다. 쉬운 문제라고 무시하지 말고 착실히 연습해가자.

파이팅!!