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

1. 문제 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 2. 풀이 과정 DFS, BFS 탐색 문제인데, 고민했던 부분은 방문체크를 어떻게 할 지였다. 방문체크는 A, B에 부었던 물의 양으로 2차원 배열을 사용했다. A, B의 물의 양이 정해지면 C의 물의 양도 정해지기 때문에, 2차원 배열로 물통들의 상태를 방문 체크 해줄 수 있다. 아래 푼 방식은 DFS를 사용했다. A에 있는 물의 양이 0보다 크다면 B, C 각각 ..

1. 문제 https://www.acmicpc.net/problem/2310 2310번: 어드벤처 게임 입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타 www.acmicpc.net 2. 풀이 과정 자주 풀어왔던 2차원 배열의 dfs가 아니라 다음에 갈 좌표가 주어지는 dfs 문제이다. 백트래킹할 때, 가격은 원래 값을 보장해줘야 하므로 temp라는 변수를 추가로 사용하여 구현하였다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; ..

1. 문제 https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 2. 풀이 과정 1. 시작점부터 중복 허용 즉, 방문 체크 없이 dfs로 탐색해서 5번 이동하는 경로를 찾는다. 2. 완성된 6자리 수는 boolean배열에 해당 수의 index에 해당하는 값을 true로 변경해주고 마지막에 true인 값을 가진 수의 개수를 출력한다. import java.io.BufferedReader; import java..

1. 문제 https://www.acmicpc.net/problem/14716 14716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net 2. 풀이 과정 8방향 탐색은 dfs로 구현하였으며, 방문 체크는 입력 값을 2로 바꾸어 표시했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N, M, map[][]; static int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, ..

1. 문제 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 2. 풀이 과정 dfs로 같은 팀끼리 인접한 수를 구하는데, 방문체크는 W, B => . 으로 변경하여 확인하였다. import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { static int N, M, result, dx[] = {-1, 0, 1, 0}, dy[] =..

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/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 2. 풀이과정 백트래킹 문제로, 각 감시카메라마다 가능한 감시 구역을 모두 탐색하며 결과값을 찾는다. N, M의 범위가 작기 때문에 전체탐색을 해도 시간 초과가 나지 않는다. 1. 전체 구역, 즉 2차원 배열을 재귀함수 simulation으로 전체 탐색을 한다. 2. 이때 해당 구역에 감시카메라가 있다면, 각 번호별로 탐색할 수 있는 구역을 탐색하고 재귀를 진행한다. 3. 감..

1. 문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 2. 풀이 과정 1. dfs 탐색으로 해당 구역과 어느 구역이 연합을 맺었는지 구한다. 이때, 연합을 맺은 구역의 좌표와 인구 수의 합을 저장해둔다. 2. 연합 하나를 구할 때마다, 각 구역의 인구수를 (연합의 인구합)/(연합 구역 수)로 업데이트 해준다. 3. boolean값으로 연합을 찾았는지 확인하며, 연합이 없을 경우 반복문을 종료한다. import java.io...

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/3671 3671번: 산업 스파이의 편지 각 테스트 케이스에 대해 종이조각을 적절히 배치해서 만들 수 있는 서로 다른 소수의 개수를 출력한다. 이때, 모든 종이 조각을 사용하지 않아도 된다. (7과 1이 있을 때, 만들 수 있는 소수는 7, www.acmicpc.net 2. 풀이 과정 1. 주어지는 input의 숫자 하나하나를 int[]로 변환한다. 2. 순열을 이용하여 모든 경우의 수를 탐색한다. 3. 집합으로 중복된 값은 소수 판단 여부에서 제외한다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashSet; import java...