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

문제) 백준 - DFS - 맥주 마시면서 걸어가기

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

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

 

좌표를 모두 입력받아 20*50을 넘는 점을 제외하고 graph에 인접 리스트 형태로 나타냅니다. DFS를 통해 탐색하면서 visited [N+1] 번째를 방문 여부에 따라 'happy' 또는 'sad'를 출력합니다. 

 

C++ 소스코드)

	while (tc--) {
	for (int i = 0; i < MAX; ++i)
	graph[i].clear();
	memset(visited, false, sizeof(visited));
	cin >> N;
	for (int i = 0; i < N + 2; ++i)
	cin >> coord[i].first >> coord[i].second;
	for(int i = 0; i <N + 2;++i)
	for (int j = i + 1; j < N + 2; ++j)
	if (dist(coord[i], coord[j]) <= 20 * 50) {
	graph[i].push_back(j);
	graph[j].push_back(i);
	}
	dfs(0);
	if (visited[N + 1])
	cout << "happy" << endl;
	else cout << "sad" << endl;
	}

view raw 9205.cpp hosted with ❤ by GitHub

 

Full code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%205000~9999/9205_%EB%A7%A5%EC%A3%BC%20%EB%A7%88%EC%8B%9C%EB%A9%B4%EC%84%9C%20%EA%B1%B8%EC%96%B4%EA%B0%80%EA%B8%B0.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions