백준 24955번 숫자 이어 붙이기

문제 설명

이번 문제는 N개의 집과 N-1개의 도로에서 집마다 1~N까지 번호가 붙어있고, 두 집 사이를 이동할 경우 도로를 이동할 때, 출발지점부터 끝지점까지 이동하면서 집의 번호를 이어붙이면 어떤숫자가 되는지 맞추는 문제입니다.

 

문제 풀이

아이디어

시작집과 끝집 사이를 최소로 이동하는 방법

bfs를 이용해 최소 이동 방법을 구할 수 있습니다.

queue에 넣을 원소는 [{이어붙인 번호:string}, {현재 집}]의 배열 형태입니다.

 

집 번호와 현재 집

문제에서 제시된 집에는 1~N의 번호가 붙어있습니다. 만약 집 1에 번호 3번이 붙어있는 경우 집의 번호는 3번이고 현재 집은 1이라고 표시하겠습니다. (헷깔릴 수 있으므로 위와 같이 정의했습니다.)

 

풀이

bfs

[시작 집의 번호, 시작 집]배열을 queue에 넣고 끝 집이 나올 때까지 while문을 반복합니다.

 

while문 내부

queue의 첫 번째 원소를 dequeue합니다.

그 다음 해당 집에서 갈 수 있는 집 중 아직 방문하지 않은 집을 [{현재까지 이어붙인 번호+현재 집 번호},현재 집]을 enqueue합니다.

 

현재 dequeue된 집이 마지막 집이라면 while문을 break하고 1,000,000,007로 나눈 값을 출력합니다.

 

 

 

해결

이번 문제는 다시 보니 쉽게 해결할 수 있었을 것 같은데 문제를 풀 때는 13번이나 시도했던 문제입니다....

 

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

24955번: 숫자 이어 붙이기

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/24955.py