네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/1189 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다 www.acmicpc.net 2. 풀이 과정 1. dfs로 모든 경로 탐색을 한다. 2. 도착점에서 해당 경로가 K면 result+=1 아니면, 해당 경로는 그만 탐색하도록 한다. 또한, 아직 도착점이 오지 않았지만 경로가 이미 K이상이면 더 이상 탐색할 필요가 없으므로 탐색을 종료한다. import java.io.BufferedReader; import java.io.Inp..

1. 문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 2. 풀이 과정 1. 4방향 탐색하면서 빙산이면 dfs탐색하고, 빙산이 아니면 cnt+1을 한다. 2. 한 번 dfs탐색이 끝났는데, 또 dfs탐색할 곳이 남았다면 분리되었다는 것으로 판단하고 종료한다. 3. dfs 탐색이 끝나고 2중 for문으로 전체를 돌면서 주변 0의 개수만큼 숫자를 빼준다. import java.io.BufferedReader; import java.io.I..

1. 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 2. 풀이과정 MST 문제로 Kruskal이나 Prim으로 접근할 수 있다. 노드 수가 1000개, 간선 수가 최대 100,000로 N(N-1)보다 10배 적은 수이다. 따라서 여기서는 kruskal을 활용해서 풀었다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { s..

1. 문제 https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 2. 풀이 과정 1. 시작점에서 출발해서 bfs로 탐색한다. 2. PriorityQueue를 사용해서 변환 횟수가 적은 것부터 탐색하면, 해당 블럭마다 변환횟수가 가장 적은 경로로 탐색하게 되므로 도착점에 오는 순간 바로 종료한다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Prior..

1. 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 2. 풀이 과정 - bfs import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { public static void ma..

1. 문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 2. 풀이 과정 1. (0, 0)에서 시작해서 치즈 있는 곳을 만나면, 치즈 있는 곳에 +1을 해준다. 2. 치즈가 있는 곳이 3이 되는 순간 2면이 외부와 닿아있다는 의미이므로 다음 탐색할 노드에 추가해준다. 3. next = 다음 탐색할 노드들의 모음으로 각 노드마다 dfs로 치즈 있는 곳을 만나면, 치즈 있는 곳에 +1을 하고 2단계를 반복한다. import java...

1. 문제 https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 2. 풀이 과정 MST 문제이고, kruskal와 prim이 떠올랐다. 두 가지 알고리즘을 각각 사용해서 두 번 풀어봤는데, 간선의 개수가 많기 때문에 kruskal보다 prim이 훨씬 빨랐다. 1. Kruskal 더보기 import java.io.*; import java.util.*; public class Main { static int N, p[]; public static Pr..

1. 문제 https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 2. 풀이 과정 처음 주어진 감염된 컴퓨터로 부터 다른 컴퓨터들이 몇 초 안에 감염되는지 확인해야 한다. 감염된 컴퓨터들 중에 시간이 가장 많이 걸린 시간이 감염하는 데 걸린 시간이다. 이때, 걸리는 시간이 모두 다르므로 BFS가 아닌 다익스트라를 사용해야 한다. import java.util.*; import java.io.*; public class Main { static int T,..

1. 문제 https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 2. 풀이과정 1. 조합으로 바이러스를 놓을 장소를 선택한다. 2. M개를 선택하면, simulation인 dfs를 실행하여 걸린 시간을 count한다. 3. 바이러스를 퍼트린 공간 < (전체)-(벽의 수) 이면, 바이러스를 모두 못 퍼트린 상태로 처리한다. import java.io.*; import java.util.*; public class Main { private static int ..

1. 문제 https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 2. 풀이 과정 bfs나 dfs 아무거나 편한 걸로 선택해서 풀면 되는 문제 같다. 아래 풀이에서는 돌아본 곳을 또 방문하지 않기 위해서 bfs를 썼다. 무조건 바깥 테두리엔 치즈가 없으므로, 테두리 0, 0에서 시작해서 1을 만나면 값을 0으로 바꾸고 Queue에 쌓아주었다. 또 다음 Queue의 요소를 돌면서 또 1을 만나면 같은 작업을 반복해주었다. 하지만 N, M의 크기가 작은 편이라 전..