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

1. 문제 https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 2. 풀이과정 1. 울타리가 아니면 dfs 탐색 시작 2. 탐색하면서 늑대와 양의 수를 센다. 3. 탐색이 끝나면 늑대와 양의 수를 비교해서 결과에 반영한다. import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { static int N, M, dx[] = {-1, 0, 1, 0..

1. 문제 https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 2. 풀이과정 방법 1. BFS 더보기 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int damage[][] = new ..

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/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의 크기가 작은 편이라 전..

1. 문제 https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 2. 풀이 과정 1. 사이클 찾기(DFS) 모든 경로를 돌다가 아래 두 조건을 만족하면, 사이클이므로 return true를 하고 사이클 요소에 true표시 1) 방금 전에 방문한 노드 != 다음에 방문할 노드 2) 이미 방문한 노드 dfs로 돌아가다가 출발점을 마주치면 return false로 사이클 요소 true표시를 종료한다. 2. 사이클에서부터 거리 찾..

1. 문제 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 2. 풀이과정 이 문제는 dfs나 bfs 둘 중 하나로 풀 수 있을 것 같은데, dfs를 선택한 이유는 n, m의 최대 크기가 100으로 작은 편이라 stack이 최대 100x100개정도 밖에 안 쌓이며, 코드도 더 짧기 때문이다. import java.util.*; import java.io.*; public class boj1743 { sta..

1. 문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 2. 풀이과정 1. 0이 모여있는 구간마다 0의 개수를 센다. 2. 벽에서 4방향을 보면서 인접한 0의 구역에 있는 0의 개수를 더해준다. import java.io.*; import java.util.*; public class Boj16946 { static int N, M, map[][], no; static int dx[] = {-1, 0, 1, 0}, dy..

1. 문제 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 2. 풀이과정 1. 팀 나누기(조합) 조합의 특성을 이용하자면, 아래 문제에서 nC1과 nC(n-1)은 같은 경우라고 볼 수 있다. 따라서 n/2개까지만 뽑는 조합을 작성하여 simulation을 돌린다. 왜 같은 경우인지 설명하자면, 두 팀으로 나누어 두 팀의 값 차이를 결과로 내기 때문에, 각 팀이 빨간팀인지 파란팀인지는 상관없다. 빨간팀의 값이 1이고 파란팀이 3일 때와 빨간팀의 값이 3이고 파란팀이 ..