본문 바로가기

너비우선탐색8

[백준] 13265 색칠하기 (Java) [13265 색칠하기] 난이도: 골드5 13265번: 색칠하기 각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다. www.acmicpc.net 문제 입력 출력 [아이디어] 먼저 동그라미들을 노드로 갖고 연결된 직선을 엣지로 생각해주었다. 그 후 노드에 대해 DFS를 사용하여 연결된 노드 두개가 같은 색이라면 impossible, 아니라면 possible을 출력하도록 하였다. [JAVA 코드] import java.io.*; import java.util.*; public class BJ_G5_13265_색칠하기 { static BufferedReader br = new BufferedR.. 2022. 5. 29.
[백준] 17141 연구소2 (Java) [17141 연구소2] 난이도: 골드4 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 문제 입력 출력 [아이디어] 바이러스가 들어갈 자리에서 M개를 조합으로 선택하여 완전 탐색하는 방법이다. 사방면으로 바이러스가 퍼져나갈 수 있고, 최소 시간을 구하는 문제이기 때문에 BFS를 사용하였다. 그 외는 단순한데, Queue에 처음 바이러스 자리 M개를 초기화 시켜줄 때 전체 맵을 탐색할지 M개를 바로 넣을지를 고민하였다. 직접 해본 시간이 별로 차이나지 않으므로 아무거나 써도 될 것 같다! [JAVA 코드] 1. M개를 바.. 2022. 5. 20.
[백준] 18405 경쟁적 전염 (Java) [18405 경쟁적 전염] 난이도: 골드5 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 문제 입력 출력 [아이디어] 사방으로 바이러스가 퍼져나가므로 BFS를 활용하면 된다. 이 때, 매 초다마 번호가 낮은 종류의 바이러스부터 증식하므로 단순 Queue를 사용하면 구현이 조금 복잡해질 수 있다. 따라서 나는 우선순위 큐를 사용해주었다. Point 클래스를 생성하여 바이러스의 위치, 종류, 걸린시간을 관리해주었고, 시간과 바이러스 종류로 우선순위를 정해주었다. 그 후는 일반 BFS.. 2022. 5. 5.
[백준] 14442 벽 부수고 이동하기 2 (Java) [14442 벽 부수고 이동하기 2] 난이도: 골드3 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 입력 출력 [아이디어] 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 위의 문제의 업그레이드 버전이다. 저 문제를 먼저 풀고 지금 문제를 푸는 것이.. 2022. 5. 1.
[백준] 2206 벽 부수고 이동하기 (Java) [2206 벽 부수고 이동하기] 난이도: 골드4 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 입력 출력 [아이디어] 빠르게 목적지에 도착하는 경우를 구해야하기 때문에 BFS를 활용하면 된다. 하지만 벽을 한 번 파괴할 수 있으므로 파괴한적이 있는지 따로 체크해주며 돌아준다. 그래서 Point 클래스를 따로 만들어주고, 안에는 위치와 이동한 횟수, 파괴했는지를 저장해준다. static class Point { int r, c, cnt; boolean distroyed; // 파.. 2022. 5. 1.
[백준] 1600 말이 되고픈 원숭이 (Java) [1600 말이 되고픈 원숭이] 난이도: 골드4 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 문제 입력 출력 [아이디어] 문제 자체는 BFS를 활용하면 된다는 것이 바로 보인다. 하지만, 일반 BFS를 활용했다가는 틀렸습니다를 만나게 될 것이다. 이 문제는 말의 이동 횟수에 따라 방문 여부를 다르게 관리해줘야 한다는 것이 문제의 핵심이다. visited 배열을 3차원으로 만든다. visited[i][j][k] 에서 i는 행, j는 열, k는 말처럼 움직인 횟수를 나타낸다. 여기서 k는 0~.. 2022. 4. 19.
[백준] 2636 치즈 (Java) [2636 치즈] 난이도: 골드4 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 문제 입력 출력 [아이디어] 이 문제는 BFS를 사용하면 된다고 바로 감이 올 것이다. 하지만 어려운 부분은 어떻게 외부 공기가 닿는 부분만 체크를 하는가이다. 문제를 해결하는 방법은 거꾸로 생각하기이다. 보통 치즈를 너비 우선 탐색하는 방법을 사용하지만, 이 문제는 바깥의 공기를 너비 우선 탐색하여 체크해주는 것이 포인트이다. 먼저 바깥의 공기를 너비 우선 탐색해서 어느 부분이 공기인지 체크해준다. 그 후 전체를 탐색하면서 치즈인 경우.. 2022. 4. 17.
[백준] 1202 유기농 배추 (Java) [1012 유기농배추] 난이도: 실버2 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 입력 출력 [아이디어] 배추밭을 완전 탐색한다. 배추가 심어져 있는 위치에서 BFS를 사용하여 서로 인접해있는 배추를 체크한다. 몇 개의 배추 더미가 있는지 세어준다. [JAVA 코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.. 2022. 3. 3.

티스토리툴바