(JAVA) 백준 9205번 : 맥주 마시면서 걸어가기 --- [BFS]

https://www.acmicpc.net/problem/9205

9205번: 맥주 마시면서 걸어가기

 

안녕하세요.

 

 

플로이드 - 와샬 알고리즘을 사용하라했지만

 

BFS 로 접근하여 해결했습니다.

 

 

바로 매커니즘을 짚어보기 전에

 

유의할 부분을 체크하겠습니다.

 

 

  -  1개당 50미터, 최대 20개 => 즉, 한 지점에서 다른 한 지점으로 넘어갈 때 마다 최대 1000미터까지만 이동할 수 있다.

 

  -  두 좌표 사이의 거리 = x좌표 값의 차이 + y좌표 값의 차이

 

  -  종료 조건 : 상근이네 ----> 패스티벌 목적지 까지 가는 경우가 존재하는지 안하는지. 그래서 하나라도 경우가 존재하면 무조건 갈 수 있는 것이다.

 

 

 

매커니즘

---

  1)  x와 y값을 입력받을 때, 한 줄(한 지점)당 하나의 index를 가진다고 가정하기. 즉, n을 입력받으면, 0 ~ n+1 (상근이네, 패스티벌 지점 포함) 의 index가 생성됩니다. 

 

  2)  별도의 클래스를 선언하고, 입력으로 x, y 받을 시 하나의 클래스 객체를 생성해서 배열에 저장해둡니다.

 

  3)  2차원 boolean 배열 생성 ([x][y] 라고 할 때, x index 지점 -> y index 지점 이동 가능 여부가 원소의 값이 됩니다.)

ex) boolean[2][3] = true 이면, 2번 지점에서 3번 지점으로 1000미터 이내로 이동이 가능하다는 뜻.

 

  4)  한 번 클래스 객체 배열을 2중 for문으로 순회하면서,  두 지점의 거리가 1000미터를 벗어나는지 확인해서 boolean 배열의 값을 변경합니다.

    *** 이 때, 두 지점의 거리가 1000미터 이내라면, x -> y , y -> x 모두 성립하기 때문에 양방향 그래프라고 생각하고 배열의 값을 변경해야 합니다.

 

  5)  방문 여부 체크하는 boolean 1차원 배열을 생성해서, 이 것과 같이 BFS를 진행합니다.

만약 이전에 방문했다면, 큐에 넣지 않습니다.

 

  6)  큐가 empty 되기 전까지 종료 지점에 도착하면 가능! 도착 못하면 불가능!

 

 

 

이상입니다.

 

이 매커니즘 혹은 문제 해결항법에 대해 궁금하신 사항은 댓글로 질문해주세요.

 

 

감사합니다!

 

 

 

소스코드

---