본문 바로가기

분류 전체보기361

[BOJ]9205번: 맥주 마시면서 걸어가기 www.acmicpc.net/problem/9205 그래프 탐색문제입니다. 상근이네 집 -> 페스티벌 장소까지 중간에 편의점을 경유하든 안하든 도달할 수 있는지 묻습니다. 한 장소에서 맥주를 20개까지 충전가능하기에 정점과 정점사이의 거리가 1000m 이하일 때만 이동 가능합니다. 바꿔말하면, 1. 플로이드 알고리즘을 통해 정점과 정점 사이의 거리를 모두 구하기 2. BFS를 돌면서 상근이네 -> 페스티벌 장소까지 이동가능 여부 판단 위 두 가지 과정을 거치면 됩니다. 다음 노드를 큐에 넣을 수 있는지 판별여부는 현재 노드와 다음 노드의 거리가 1000m 이하인지 체크하면됩니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ9205.cc 2020. 9. 13.
[BOJ]1389번: 케빈 베이컨의 6단계 법칙 www.acmicpc.net/problem/1389 BFS, 플로이드-와샬 등 다양한 형태로 해결할 수 있습니다. 저는 플로이드로 해결했습니다. "dist[i][j] = i와 j가 연결되어 있는 거리"로 정의합니다. 초기값은 dist[i][j]= ∞로 두고, 입력이 주어져 있는 경우만 dist[i][j] = 1로 셋팅을 합니다. 그 다음에 플로이드를 돌면서 dist[i][j] > dist[i][mid] + dist[mid][j] 이면 dist[i][j] = dist[i][mid] + dist[mid][j] 로 갱신하면 됩니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ1389.cc 2020. 9. 12.
[BOJ]1613번: 역사 www.acmicpc.net/problem/1613 역사의 우선순위는 그래프 문제로 바라볼 수 있습니다. 그래프 문제 관점에서 모든 정점에서 다른 모든 정점으로의 관계가 궁금한 것이니 플로이드 알고리즘을 써서 해결할 수 있습니다. eventTable[eventA][eventB] == 1 이면, eventA가 B보다 먼저 일어난 것이고, eventTable[eventB][eventA] == 1 이면, eventB가 A보다 먼저 일어난 것이고, eventTable[eventA][eventB] == 0 이면, 둘 사이에는 아무런 관계가 없는 것입니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ1613.cc 2020. 9. 11.
[BOJ]1865번: 웜홀 www.acmicpc.net/problem/1865 라이님 블로그(blog.naver.com/kks227/220796963742)의 풀이를 참고하여 해결했습니다. 임의의 정점에 대해 모두 벨만포드를 돌 수 없으므로 그래프를 BFS 탐색을 통해 컴포넌트로 나눠주고, 각 각의 컴포넌트에 대해서만 한 번씩 벨만포드를 돌면 됩니다. 하나의 컴포넌트라도 컴포넌트내에 음의 싸이클이 있다면 YES, 아니면 NO를 출력하면 됩니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ1865.cc 2020. 9. 11.

티스토리툴바