본문 바로가기

분류 전체보기361

[BOJ]1800번: 인터넷 설치 www.acmicpc.net/problem/1800 justicehui님의 풀이를 보고 해결했습니다. (justicehui.github.io/usaco/2019/07/12/BOJ1800/) 단순히 DFS를 돌려버리면 터지므로 다익스트라 + 결정 문제로 바꿔서 해결합니다. "특정 가중치 이하의 간선으로만 경로를 구성할 수 있는가?"를 결정하는 문제로 특정 가중치가 넘는 간선에 대해서는 1의 가중치를 주고 특정 가중치가 넘지 않는 간선에 대해서는 0에 가중치를 주어 다익스트라를 돌립니다. 만든 최단 경로가 K 이하의 가중치로 도달가능하다면 이 값은 가능한 값으로 저장해놓고 mid를 더 줄여서, 더 작은 가중치로 다시 연결 시켜봅니다. 만든 최단 경로가 K 이하의 가중치로 도달이 불가능하다면 mid를 올려서 .. 2020. 10. 10.
[BOJ]19237번: 어른 상어 www.acmicpc.net/problem/19237 시뮬레이션 문제입니다. 이 문제를 풀 때 가장 중요한 것은 문제 시나리오를 쪼개는 방식이라고 생각합니다. 제가 해결한 순서는 아래 4가지 순서로 문제를 나눠서 해결했습니다. 1. 모든 상어 이동 2. (상어가 이동을 모두 마쳤으니) 기존에 상어가 냄새뿌려놓았던 칸 count-- 3. 상어가 이동 후 겹치는 칸이 있는지 check -> 겹치면 상어 kill 4. 상어가 새로 이동한 칸에 냄새 뿌리기 N제한이 작기 때문에 시뮬레이션으로 구현만 하면 됩니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ19237.cc 2020. 10. 10.
[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.

티스토리툴바