본문 바로가기

Algorithm283

[BOJ]1043번: 거짓말 www.acmicpc.net/problem/1043 지민이가 거짓말을 했다는 걸 아는 사람과 같은 컴포넌트 내에 있는 사람은 모두 제외하면 됩니다. 이걸 구하는 방식은 아래와 같습니다. 1. 맨 처음 입력받은 파티 정보로 지민이가 거짓말을 하는 걸 아는 사람들과 바로 연결되어 있는 사람들을 구합니다. 2. 그 후에 플로이드 알고리즘이 N^3으로 i -> j의 연결관계를 1~k까지 중간지점을 경유해서 구하는 것처럼, N번 루프 밖에 루프를 돌면서 (한 사람이 다른 사람과 관계를 맺을 때 최대 걸리는 길이는 N-1번) i,j가 연결관계에 있는데, 둘 중 한명이라도 거짓말을 안다면 나머지 한 명도 그 사실을 알도록 체크해줍니다. 3. 2번과정을 마친 후 파티 정보를 순회하면서 파티 내에 거짓말 사실을 아는 사.. 2020. 10. 7.
[BOJ]1976번: 여행 가자 www.acmicpc.net/problem/1976 여러 가지 방법으로 풀 수가 있겠습니다. 제가 해결한 방법은 Floyd + BFS 입니다. 1. 플로이드를 통해 모든 가능한 정점쌍을 연결해줍니다. 2. 주어진 플로이드를 가지고 N개의 노드에 대해 BFS를 돌아서 컴포넌트를 나눠줍니다. 3. 여행 경로에 속한 노드가 모두 한 컴포넌트에 속해있다면 순서가 어떻든 모두 방문이 가능합니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ1976.cc 2020. 10. 6.
[BOJ]18428번: 감시 피하기 www.acmicpc.net/problem/18428 시뮬레이션 문제입니다. 1. N제한이 작으므로 전체 빈 칸갯수에서 임의로 3칸을 뽑아봅니다. (nC3) 2. 뽑은 3칸을 벽으로 바꾸고 모든 선생님 칸에 대해 4방향 탐색을 해봅니다. 3. 한 번이라도 학생들을 못 찾았다면 YES, 그런 경우가 없었다면 NO 입니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ18428.cc 2020. 10. 6.
[BOJ]17182번: 우주 탐사선 www.acmicpc.net/problem/17182 시작점에서 출발해서 모든 점을 전부 순회할 때 최솟값을 구하는 문제입니다. 문제 조건이 MST나 단순 다익스트라와는 약간 다릅니다. 1. 플로이드를 통해 모든 정점쌍 간의 최소거리를 구합니다. 2. N제한이 작으므로 순열을 통해 방문할 순서를 미리 정한 후 순서대로 방문해봅니다. 위 과정을 통해 가장 짧은 경로를 구할 수 있습니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ17182.cc 2020. 10. 6.

티스토리툴바