hcjy97   3년 전

코테에서 최단 경로의 개수를 구하는 문제가 나왔습니다.

최단 경로의 길이는 BFS로 풀면 되고 경로의 개수는 BFS 해서 나온 visited배열에서 trace하면 될 것 같았는데 잘 안 되었습니다.

다음에 비슷한 유형의 문제가 나오면 꼭 풀어보고 싶습니다.

혹시 비슷한 유형의 문제가 백준에 있는지, 있다면 어떤 문제가 있는지 알고 싶습니다.

WeissBlume   3년 전

https://www.acmicpc.net/proble...

간선의 가중치가 서로 다를 수 있어서 bfs만으로는 최단 경로를 구하기 힘들다는 점이 다르지만 적어둡니다.

hcjy97   3년 전

감사합니다!! 정확히 제가 찾던 그 문제입니다

hijkl2e   3년 전

어디 코테였는지 알려주실 수 있나요?

pill27211   3년 전

@hijkl2e

우아한 테크 캠프 6기 1차 코딩 테스트 였던 것 같네용

hijkl2e   3년 전

@pill27211 저도 아까 참가했는데 최단 경로 키워드만 들어 있는 순수 dp 문제였어서.. 혹시 혼동하셨나 하고 여쭤봤습니다 :)

hcjy97   3년 전

우아한 테크 캠프 6기 1차 코딩테스트 맞습니다.

그것도 그렇고 전에 롯데정보통신 코테 봤을 때도 똑같은 유형의 문제가 나왔었거든요.

지금까지 코테에서 두 번이나 만난 셈인데 항상 잘 안 풀려서 연습해 볼까 하고 질문 올려봤습니다!

@hijkl2e님 댓글을 읽으니 제가 왜 항상 못 풀었는지 알겠네요. 키워드를 잘못 잡았으니 문제가 풀릴 리가 없죠..

dp 문제 쪽에도 비슷한 문제가 있나 찾아봐야겠습니다. 감사합니다!

hcjy97   3년 전

위 댓글을 보고 비슷해 보이는 문제를 더 찾아보고 있습니다.

발견할 때마다 이 댓글에 이어서 추가합니다.

https://www.acmicpc.net/proble...

hijkl2e   3년 전

https://www.acmicpc.net/proble...

약간 더 복잡하지만 유사한 문제입니다.

원본 문제에서 최단 경로로 이동한다는 조건은 위쪽과 오른쪽 방향으로만 이동할 수 있다는 뜻이었습니다.

댓글을 작성하려면 로그인해야 합니다.