본문 바로가기

전체 글200

[BOJ]17472번: 다리 만들기 2 www.acmicpc.net/problem/17472 시뮬레이션 + MST 문제입니다. 1. BFS를 돌려서 컴포넌트간 최단 거리를 구해서 인접 그래프/행렬을 완성합니다. 2. 완성한 인접 그래프/행렬을 바탕으로 MST를 구하면 됩니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ17472.cc 2020. 10. 13.
[BOJ]17025번: Icy Perimeter www.acmicpc.net/problem/17025 BFS 문제입니다. 컴포넌트를 구하고 각 컴포넌트에 대한 칸의 갯수와 둘레를 구해야 합니다. 넓이 = 컴포넌트의 칸의 갯수 둘레 = 컴포넌트를 위아래좌우 4방향으로 BFS로 순회하면서 마주치는 빈 칸 + 범위 벗어나는 칸의 수 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ17025.cc 2020. 10. 13.
[BOJ]17086번: 아기 상어 2 www.acmicpc.net/problem/17086 BFS 문제입니다. N 제한이 작으므로 N*M에 존재하는 전체 빈칸에 대해 각 각 BFS를 돌려도 시간 제한안에 통과할 수 있습니다. BFS를 진행할 때 한 번에 같은 거리는 모두 탐색하도록 하여 아기 상어를 만나면 거리를 리턴하도록 했습니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ17086.cc 2020. 10. 12.
[BOJ]2174번: 로봇 시뮬레이션 www.acmicpc.net/problem/2174 시뮬레이션 문제입니다. 좌표 변환만 본인에게 편한 방식으로 하면 해결할 수 있습니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ2174.cc 2020. 10. 12.
[BOJ]17406번: 배열 돌리기 4 www.acmicpc.net/problem/17406 시뮬레이션 문제입니다. 주의해야 할 특이사항은 없는 거 같습니다. 1. parameter로 2개의 좌표를 받습니다. (좌측 상단, 우측 하단) 2. 좌측상단, 우측하단 2개의 좌표를 기준으로 4개 꼭지점 좌표를 구합니다. 3. 구역을 4개로 나눠 (9시 방향, 12시 방향, 3시 방향, 6시 방향) 한 칸씩 시계방향으로 밀어줍니다. 4. 좌측상단 좌표 (x,y) -> (x+1,y+1)로 갱신, 우측하단 좌표 (x2,y2) -> (x2-1,y2-1)로 갱신 후 1번 과정을 반복 회전을 위한 루프 횟수는 맨 처음에는 2*S만큼 돌고 좌측상단, 우측하단 좌표가 갱신되어 재귀가 생길 때 마다 2칸씩 줄어듭니다. 문제를 시뮬레이션하면 고려해야할 부분들에 대해 .. 2020. 10. 12.
[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.