[백준] 9205번: 맥주 마시면서 걸어가기 (C++ 풀이)

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

풀이

점과 점사이의 맨해튼 거리를 계산하고

그 거리가 20병*50m=1000m 이내이면 그래프로 저장한다.

dfs로 시작점인 0부터 탐색을 하는데

첫번째 예제에서는 모든 좌표가 1000이내에 있어서 그래프가 하나로 연결되어있다.

그래서 시작점에서 도착점까지 무사히 갈 수 있는데

두번째 예제에서는 중간에 1000이내에 갈 수 없는 지점이 있다.

그래서 그래프가 2개가 되는데 시작점에서부터 dfs탐색을 할 경우 도착점까지 탐색을 하지 못하게 된다.

dfs탐색을 마친후 도착점에 방문했는지 여부에 따라 happy or sad를 출력하면 된다.

 

코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/9205.cpp

결과