문제https://www.acmicpc.net/problem/17836 여담예전에 BFS 문제를 풀 때, "탐색 도중에 상태가 변하는 것이 있다면 3차원 배열로 방문 처리를 진행하자!"라는 것을 외웠다. 그래서 빠르게 아이디어를 떠올릴 수 있었다. 역시 코테는 많은 유형을 접해보고 푸는 게 답인 듯하다. 많이 풀어보자! 풀이용사가 (1, 1)에서 (N, M)까지 상하좌우로 이동하여 공주에게 도달할 수 있는 최단 시간을 구하는 것이므로, BFS 탐색을 수행하면 된다. 이때, 그람을 획득하면 성 내부의 벽을 부술 수 있다. 부술 수 있는 벽의 개수는 제한이 없으므로, 그람을 획득한다는 것은 벽이 없어진다는 것이랑 동일한 의미를 가진다.  따라서 그람을 획득하지 못한 경우와 그람을 획득한 경우의 2가지로 나누..

문제https://www.acmicpc.net/problem/7576 여담익어있는 토마토가 여러 개 주어질 수 있으므로, 익어있는 토마토들의 위치를 미리 큐에 넣는 작업이 필요하다. 이 과정에서 큐에 넣기만 하고 방문 처리를 하지 않아서 틀렸었다.. 뒤늦게라도 알아서 다행이지만 코테였다면 이유를 찾느라 고생했을 것이다. 아찔... 익숙한 문제라고 뇌 빼고 풀지 말고 차근차근 풀도록 하자! 풀이토마토들이 모두 익을 수 있는 최소 일수를 구하는 문제이다. 즉, 최단 거리를 구하는 문제와 비슷하므로 BFS 탐색을 수해하면 된다.  문제 풀이 과정은 다음과 같다.익은 토마토들이 1개 이상 주어지므로, 익은 토마토들의 위치를 큐에 저장하고 방문 처리한다.BFS 탐색을 수행하여 토마토들이 익는 일수를 구한다.box..

문제https://www.acmicpc.net/problem/10026 여담골드5치고는 간단하게 BFS 탐색을 수행하면 되는 것이라 쉽게 풀 수 있었다! 풀이같은 색으로 이루어진 구역의 개수를 찾는 것이므로, BFS 또는 DFS 탐색의 호출 횟수를 구하는 것과 같다. 따라서 단순하게 BFS/DFS 탐색을 수행하면 된다. 이때, 적록색약인 사람은 빨강과 초록을 구분하지 못하므로 초록(=G)을 빨강(=R)으로 변경한 뒤 탐색을 수행하면 된다. 자세한 내용은 아래의 코드를 참고하면 된다. 코드import java.io.*;import java.util.*;public class Main { static int N; static char[][] pictureO, pictureX; // O: 적록색약 ..

문제https://www.acmicpc.net/problem/5427 여담테스트 케이스마다 큐를 초기화하지 않아서 틀렸었다. 이런 실수가 진짜 치명적인건데....ㅎ 맞는 것 같은데 틀리면 제일 먼저 초기화와 변수를 확인하자..  풀이빌딩을 탈출할 수 있는 최소 시간을 구하는 것이므로, BFS 탐색을 이용하면 된다. 1초마다 불이 퍼지고 상근이가 이동하며, 상근이는 불이 퍼진 곳이나 퍼질 곳으로 이동할 수 없다. 따라서 불을 먼저 퍼뜨린 후, 상근이를 이동시키는 방법을 반복하면 된다. 이때, 불이 더 이상 퍼질 수 없더라도 상근이가 탈출을 하는 데에는 아무 상관이 없다. 따라서 상근이가 더 이상 움직일 수 없을 경우(= 큐가 빈 경우)에만 BFS 탐색을 종료하면 된다. 자세한 내용은 코드를 참고하면 된다...

문제https://www.acmicpc.net/problem/16918 여담처음 문제를 읽고 어려울 것 같아 겁을 먹었지만 문제에서 주어지는 힌트를 통해 쉽게 풀이를 떠올릴 수 있었다. 그렇지만 코테에서는 이런 힌트가 잘 주어지지 않으니까 문제만 보고 풀 수 있도록 노력해야 되겠다. 풀이이 문제는 다음과 같은 규칙으로 진행된다. 처음 & 1초: 아무것도 하지 않음2초: 모든 칸에 폭탄 설치3초: 3초 전에 설치한 폭탄 폭발4초: 모든 칸에 폭탄 설치4초: 3초 전에 설치한 폭탄 폭발... 위의 규칙을 통해 짝수 초일 때는 모든 칸에 폭탄이 설치되는 상태가 된다는 것을 알 수 있다. 따라서 N이 2의 배수라면 모든 칸에 폭탄이 설치된 상태를 출력하면 된다. 홀수 초일 때는 폭발이 발생한다. 즉, 2초마다 ..

문제https://www.acmicpc.net/problem/15649 여담DFS & 재귀에 약해서 살짝 헷갈렸다. 관련 문제들이 많은데 풀어보면서 좀 익혀야 할 듯! 풀이DFS와 백트래킹을 사용해서 풀이하면 된다. 이때, 같은 수는 두 번 사용할 수 없으므로 used 배열을 추가해서 해당 수의 사용 여부를 기록해야 한다.  각 수에 대해 탐색을 수행한 뒤, 사용 처리를 취소하지 않으면 해당 수를 더 이상 사용할 수 없다. 즉, 모든 경우의 수를 다 탐색할 수 없다. 따라서 탐색이 끝나면 사용했던 수의 사용 처리를 무조건 취소(used[i] = false)해야 한다.  코드import java.util.*;import java.io.*;public class Main { static int N, M..

문제https://www.acmicpc.net/problem/1303 여담처음에 가로 크기와 세로 크기를 제대로 안 읽어서 틀렸다..ㅎㅎ 가로 크기가 N, 세로 크기가 M이다! 잘 읽고 문제를 풀자. 풀이W로 이루어진 영역에 존재하는 우리 병사의 수, B로 이루어진 영역에 존재하는 적국 병사의 수를 구한 뒤 white와 blue 변수에 제곱 값을 더하면 된다.  즉, BFS나 DFS를 사용해서 각 영역에 존재하는 같은 팀 병사의 수를 구해서 풀면 된다. 코드BFSimport java.util.*;import java.io.*;public class Main { static int N, M; static int white = 0, blue = 0; static char[][] map; ..

문제https://www.acmicpc.net/problem/3184 여담문제 조건에 맞게 단순하게 BFS 또는 DFS 탐색을 수행하면 되는 문제라 쉽게 풀 수 있었다. DFS로도 풀 수 있는 문제는 꼭 DFS로도 풀어보자! 너무 BFS로만 푸는 것 같다. 풀이BFS 또는 DFS 탐색을 통해 각 영역에 있는 양과 늑대의 수를 구한 뒤, 조건에 따라 수를 조정하면 된다.  한 영역 안에 있는 양의 수가 늑대의 수보다 많다면 양은 늑대를 쫓아낸다. 반대로 늑대의 수가 더 많다면 늑대는 양을 잡아먹는다. 즉, 양의 수 > 늑대의 수인 경우라면 늑대의 수를 조절하고, 양의 수 ≤ 늑대의 수인 경우라면 양의 수를 조절하면 된다.  정리하면 다음과 같다.한 영역 안의 양의 수 > 한 영역 안의 늑대 수전체 늑대의 ..

문제 https://www.acmicpc.net/problem/1743 여담 단순한 BFS/DFS 문제여서 쉽게 풀 수 있었다. 좌표가 1부터 시작하기 때문에 잘 신경써야 될 것 같다. 풀이 가장 큰 음식물의 크기를 찾으면 되므로, BFS 또는 DFS 탐색을 통해 연속된 음식물의 크기를 구하면 된다. 이때, 탐색이 끝날 때마다 음식물의 크기가 더 큰 것으로 갱신하면 된다. 코드 BFS import java.util.*; import java.io.*; public class Main { static int N, M, K, maxArea; static int[][] map; static boolean[][] visited; public static void main(String[] args) throws ..

문제https://www.acmicpc.net/problem/28069 여담0번째 계단에서 순간이동을 하면 제자리 위치라는 것을 알아차리지 못했다. 전에도 이 문제를 풀었는데 모르겠어서 그냥 풀이를 참고해서 풀고 넘어갔더니 제대로 익히지 못한 것 같다. 이번에는 꼭 다시 풀어봐야지!  풀이문제에 따르면 계단을 올라갈 수 있는 방법은 총 2가지이다. 한 칸 올라가기i + i / 2 계단으로 순간이동하기 정확히 K번째 행동에서 N번째 계단에 도달해야 미니 김밥을 먹을 수 있다고 한다. 이때, 0번 계단에서 2번 연산을 수행하면 제자리에 위치하게 된다. (0 + 0 / 2 = 0)  즉, N = 2, K = 4일 때  2번만에 N번째 계단에 도착할 수 있다면 다음과 같은 연산을 수행하면 되는 것이다. 0번 계..