백준

문제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번 계..

문제https://www.acmicpc.net/problem/2251 여담"물을 옮기는 모든 경우를 탐색하지 않고 더 쉬운 방법이나 규칙이 있지 않을까?"라는 생각으로 삽질했다..ㅎㅎ 한 번 다른 길로 빠지면 올바른 길로 돌아오기가 너무 어렵다. 처음부터 방향을 잘 잡도록 문제를 많이 풀어봐야지..!  풀이이 문제는 한 물통에서 다른 물통으로 물을 쏟아 붓는 과정을 반복하고, 물통 A가 비었을 때 물통 C의 용량을 기록하는 문제이다. 물통은 총 세 개이므로, 하나의 물통에서 다른 물통으로 물을 쏟아 붓는 경우는 총 6가지이다. 따라서 각각의 경우를 큐에 넣고 BFS 탐색을 수행하면 된다.A → BA  → CB  → AB  → CC  → AC  → B BFS 탐색 시, 이미 확인한 경우를 다시 탐색하지 않..

문제https://www.acmicpc.net/problem/2573 여담2차원 배열도 clone() 메서드를 사용하면 내용만 복제가 되는 줄 알고 사용했었다.. 그런데 답이 이상하게 나와서 확인해보니 arr 배열 값을 변경하면 map 배열 값도 변경된다는 것을 알게 되었다. clone() 메서드에 대해 검색하니 2차원 배열에는 사용할 수 없다는 것을 알게 되었다..ㅎ  전에도 이런 일이 있었던 것 같은데.. 🤦🏻‍♀️ 제발 기억하자! 1차원 배열 복제는 clone(), 2차원 배열 복제는 직접하기! 풀이빙산이 최초로 분리되는 시간을 구하기 위해서 "빙산 녹음 → 빙산의 수 확인" 과정을 반복하면 된다. 빙산의 수가 0개 또는 2개 이상일 때 반복을 종료하면 된다. 즉, 다음의 과정을 반복하면 된다...