dong_s   6일 전

안녕하세요 ㅠㅠ 알고리즘 초짜 열공중인 학생입니다.

BFS문제이지만, 우선 DFS로 짜려고 했습니다. 

그런데 틀렸습니다라는 에러가 떴구요.

타 질문글들을 읽었으나 BFS인 경우가 많고, 답글에 반례로 나온 케이스들을 돌렸을때도 정상적으로 나와서 어디서 틀렸나 감이 안옵니다.

lyzqm   6일 전

일단 이문제는 최단거리를 구하는 문제로 bfs를 풀면 훨씬 쉽게풀립니다. 

위의 코드의 문제점은 일단 2가지가 있습니다.

1. 범위 설정 : x,y값이 0이하 또는 범위 밖일 경우의 조건이 없습니다.

2. dfs탐색은 순서에따라서만 이동하기 때문에 운이 좋으면 최단거리로 이동할 수 있겠지만  값이 제대로 갱신되지 않을경우가 생깁니다.

예를 들어 x=2,y=2에서 -> (2,3) -> (3,3) -> (3,4) -> (4,4) 로 이동하는데 10의 cost가 소모됬다고 생각해봅시다.

하지만 x=2,y=2 -> (3,2) -> (3,3) -> (3,4)->(4,4)로 이동하는데 5의 cost가 소모될 수도있습니다.  위의 코드에서는 (3,3)에 대한 방문체크를 위의 탐색에서 이미 했기 때문에 새로운 값이 갱신되지 않을 수 있죠..


방문배열을 없애고 dist[i][y] ( = (1,1)에서 (i,y)까지의 거리) 배열을 수정해서 풀은 소스 올려드립니다. 

다익스트라 알고리즘도 찾아보시면 좋을 거같네요.

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