(JAVA) 백준 2917번 : 늑대사냥꾼 --- [BFS, 다익스트라]

www.acmicpc.net/problem/2917

2917번: 늑대 사냥꾼

 

안녕하세요.

 

처음에 DFS로 풀었다가 시간 초과가 발생했습니다.

 

 

그래서 여러 방법을 찾다가 BFS를 깨달았습니다.

 

 

 

로직은 간단합니다.

 

 

  1)  나무 클래스를 만듭니다. x, y, distance int 변수가 포함되어 있습니다.

 

 

  2)  맵에서 나무들의 위치를 담은 클래스 객체를 별도의 큐에 저장합니다. 이 때, 미리 거리를 담는 맵(int 2차원 배열) 에 해당 나무의 위치 초기값을 0으로 세팅합니다.

  ***  나무가 아닌 지점의 값은 Integer.MAX_VALUE 로 초기설정합니다.

 

 

  3)  BFS 알고리즘을 통해 큐에서 객체를 하나씩 꺼내면서 맵에 나무에서 떨어진 거리를 구합니다. 동서남북 4방향으로 이동이 가능합니다. 

  ***  이 때, 맵을 벗어나는지 예외를 체크하고, 시간 절약을 위해 해당 지점에 담긴 거리값과 비교하여 더 작은 경우에만 값을 갱신하고 큐에 새로 집어넣습니다.

  ***  말로 하기 힘든데, 아래 소스코드를 보시면 쉽게 이해하실 수 있습니다!

 

 

  4)  이렇게 맵에 거리를 전부 구한 다음, 시작지점부터 종료지점까지 이동하는 경로를 BFS(또는 다익스트라와 비슷) 알고리즘을 통해 구합니다.

여기서, visited boolean 2차원 배열을 별도로 만들어서 방문하지 않은 지점만 방문하여 우선순위 큐에 넣습니다.

 

 

우선순위 큐를 위해 Comparable 인터페이스를 활용할 때,

문제에서 밑줄 친 부분을 보면 

현우가 이동하는 모든 칸에서 나무와 거리의 최솟값이 가장 큰 경로 를 구하는 것입니다.

예를 들어 

 

위 지점에서의 최소 거리 : 10

아래 지점에서의 최소 거리 : 5

왼쪽 지점에서의 최소 거리 : 4

오른쪽 지점에서의 최소 거리 : 6

 

라고 하면, 네 방향 중에서 위 방향이 가장 큰 값이기 때문에 위로 이동하게 됩니다.

 

이렇게 하면서 경로를 구할 때 거리의 최솟값을 별도로 저장해뒀다가 출력하면 됩니다.

 

그래서 내림차순으로 큐에서 꺼내는 Comparable 인터페이스(compareto()) 를 구현하면 됩니다. 

 

 

 

 

말로하면 조금 헷갈리실 수 있습니다.

 

하단 소스코드를 참고하시면 더욱 쉽게 이해하실 수 있습니다!

주석도 있어요!

 

 

이상입니다.

 

감사합니다.

 

 

*** 테스트케이스 확인하기

 

1.  해당 사이트 접속

hsin.hr/coci/archive/2009_2010/

 

2.  CONTEST #2 -> Test Data 클릭 -> 파일 다운로드

 

3.  vuk 폴더에 저장된 in, out 확인

 

 

 

 

소스코드

---