본문 바로가기

백준98

백준 2146번 : 다리 만들기 문제 www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 구현 방법 단계별로 생각해주었습니다. 1. 섬 번호 새겨주기 섬끼리의 구별을 위해 dfs를 통해각 섬마다 번호를 새겨주었습니다. 2. 섬 사이의 다리 길이 구하기 섬에서 갈 수 있는 모든 다리 길이를 구해 최솟값을 찾았습니다. 각 섬의 모든 좌표에서부터 다른 섬까지의 길이를 bfs로 구해줍니다. 구현 코드 package BOJ.Gold; import java.io.BufferedReader; import jav.. 2021. 4. 9.
백준 17472번 : 다리 만들기2 문제 www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 구현 방법 문제가 복잡하여 단계별로 생각해보았습니다. 1. 섬 번호 새겨주기 섬끼리의 구별을 위해 dfs를 통해각 섬마다 번호를 새겨주었습니다. 2. 섬 사이의 다리 길이 구하기 섬에서 갈 수 있는 모든 경우를 구해주었습니다. 한 방향으로만 갈 수 있으므로 먼저 상하좌우 중 한 방향을 선택하였습니다. 선택한 방향으로 쭉 이동하여 다른 섬과 만나게 되면 다리 우선순위 큐에 추가해줍니다... 2021. 4. 5.
백준 14502번 : 연구소 문제 www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 구현 방법 벽 3개를 세울 수 있는 모든 경우의 수를 구해야합니다. 미리 빈칸의 개수와 좌표를 저장해두어 빈칸 중 3개를 구하여 구할 때마다 dfs를 돌려 바이러스를 퍼트려줍니다. 바이러스가 적게 퍼져야 안전영역이 커지므로 바이러스가 퍼지는 개수를 구해주어 이들의 최솟값을 구하여 안전영역의 최댓값을 구해줍니다. 구현 코드 package BOJ.Gold; import java.io.BufferedReader; impor.. 2021. 4. 5.
백준 1600번 : 말이 되고픈 원숭이 문제 www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 구현 방법 최소한의 동작을 구해야 하기 때문에 bfs를 사용하여 풀어주었습니다. 보통의 bfs/dfs 문제와 다르게 k번만 따로 동작을 할 수 있습니다. 평소에 방문처리를 R, C 로만 했다면 이 문제는 말 움직임을 관리하는 K까지 처리를 해줘야하므로 3차원 배열을 사용해주어야 합니다. bfs를 돌려 원숭이의 움직임으로 움직이고 만약 현재 원숭이가 말의 움직임을 할 수 있다면 말의 움직임도.. 2021. 4. 5.

티스토리툴바