본문 바로가기

Algorithm/BOJ172

[BOJ]19238번: 스타트 택시 www.acmicpc.net/problem/19238 시뮬레이션 문제입니다. N제한과 M제한이 크지 않으므로 다음 손님 탐색과, 손님 이동 모두 BFS로 해결해도 됩니다. 그래도 O(N^2 * M)이 O(20^4) 입니다. 한 가지 빼먹기 쉬운 조건이 "택시가 시작하는 위치와 손님의 시작위치가 같은 경우"가 있다는 것입니다. 이 경우에는 거리를 0으로 하고 처리하면 됩니다. 저는 이 조건 놓쳐서 계속 탐색 시작 거리를 1로 놓고 했다가 많이 틀렸었네요. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ19238.cc 2020. 10. 10.
[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.

티스토리툴바