문제https://www.acmicpc.net/problem/16236 풀이이 문제는 조건이 많이 주어지기 때문에 조건을 잘 정리해야 한다.아기 상어는 자신보다 작은 크기의 물고기만 잡아먹을 수 있다.아기 상어는 자신보다 작거나 같은 크기의 물고기가 있는 칸으로만 이동할 수 있다.잡아먹을 물고기가 없다면 엄마 상어에게 도움을 요청한다.잡아먹을 물고기가 1마리라면 그 물고기를, 2마리 이상이라면 가장 가까운 거리에 있는 물고기를 잡아먹는다.거리가 같다면 가장 위에 있는 물고기를, 같은 높이라면 가장 왼쪽에 있는 물고기를 잡아먹는다. 가장 중요한 조건은 물고기를 잡아먹는 조건이다. 그냥 BFS 탐색을 수행해서 물고기까지의 최단 거리를 구하면 된다고 생각할 수 있지만, 물고기를 잡아먹는 조건이 3가지나 주어지..

문제 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 여담문제를 제대로 읽지 않았다..^^ 주변에 지뢰가 없는 것을 열면 끝이라고 생각했는데, 예시를 보니 "주변에 지뢰가 없는 것을 열었음 → 열은 칸 주변에도 지뢰가 없음 → 연속적으로 해당 칸 열기"를 하는 것이었다. 즉, BFS/DFS 탐색을 통해 푸는 문제였다...ㅎ 문제를 제대로 읽고 해석하는 것도 실력이니 꼭..! 문제를 꼼꼼히 읽자 풀이지뢰가 없는 칸을 모두 여는 최소 터치 횟수를 구하는 문제이고, 주변에 지뢰가 없는 것을 열었는데 새로 열은 칸 주변에도 지뢰가 없다면 연속해서 칸을 열어야 한다. 즉, 지뢰가 없는 칸을 여는 최소 터치 횟수 구하기 & ..

문제https://www.acmicpc.net/problem/1600 여담예전에 풀었던 문제라 그런지 푸는 방식을 약간 외워서 푼 느낌이다. 비슷한 유형의 문제가 나오면 좋겠지만 그럴 확률은 많지 않으니 다양한 BFS/DFS 문제를 접하도록 노력해야지..! 아무튼 이와 같이 기본 조건에 상태에 대한 조건이 추가적으로 있다면 "차원을 추가해서 각각의 상태를 관리"하면 된다는 것을 기억하자! 풀이맨 왼쪽 위에서 맨 오른쪽 아래로 이동하는 최단 거리를 찾는 것이므로 BFS 탐색을 수행하면 된다.  이때, 말처럼 이동하는 횟수에 따라 방문할 수 있는 지점이 달라지므로, 말이 이동한 횟수에 따라 각각 방문 처리를 해줘야 한다. 따라서 방문 처리 배열을 vistied[세로][가로][말처럼 이동한 횟수]와 같이 3차..

13549: 숨바꼭질 3🔗 문제 링크BFS 탐색으로 최소 시간을 구하면 됨순간이동은 0초, X+1 또는 X-1로 이동하는 것은 1초가 걸리므로 순간이동을 먼저 수행하는 것이 좋음더보기24.07.01 풀이import java.io.*;import java.util.*;public class Main { static final int MAX = 100_000; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br...

문제https://www.acmicpc.net/problem/2146 여담전에 풀었을 때는 맞았었는데 이번에는 틀렸다 ^^... 각각의 육지에서 탐색을 해야 하는데 한 섬에서 최단 거리의 다리를 찾는 방식으로 수행했었다. 그렇게 하면 최단 거리를 기록하는데 오류가 생기기 때문에 올바른 답이 나오지 않는 것이었다.. 잘 생각해 보면 당연히 틀린 풀이인데 검증하지 않고 무작정 코딩을 해서 그런 것 같다.. ㅜㅜ 풀이섬 사이의 최단 거리를 구하기 위해 BFS 탐색을 수행하면 된다. 우선 섬들이 모두 1로 주어지기 때문에, BFS 탐색을 통해 각 섬을 구분해야 한다.  그 후, 각각의 좌표에서 ((0, 0) ~ (N - 1, N - 1)) BFS 탐색을 수행해서 다른 섬에 도착하는 경우에만 최단 거리를 갱신하면..

1926: 그림 🔗 문제 링크탐색하지 않았고 그림인 부분일 때 BFS 탐색하기가장 넓은 그림 찾기 ⇒  BFS 탐색하면서 그림의 넓이 구하기 & 탐색이 끝나면 최대 넓이로 갱신하기더보기24.06.17 풀이import java.io.*;import java.util.*;public class Main { static int n, m, maxArea = 0, pictureNum = 0; static int[][] picture; static boolean[][] visited; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStre..

문제https://www.acmicpc.net/problem/16932 여담시간 초과가 진짜 많이 발생했다. 오랜만에 골드 BFS 문제를 푸니까 좀 어지럽다. 계속 쉬운 문제만 푸려고 하는 습관을 버려야지 진짜.. 암튼 처음에는 map[i][j] 값이 0일 때마다 BFS 탐색을 수행하면 되겠다고 생각했다. 그치만 위와 같이 시간 초과가 발생했다. 시간을 줄일 수 있는 방법으로 고쳐나갔는데도 계속 시간 초과가 발생해서 결국 다른 분의 아이디어를 참고했다.  항상 문제를 풀 때 시간 초과를 고려해서 푸는 습관을 들이도록 노력해야지..! 풀이위에서 언급했듯이, map[i][j]의 값이 0이면 BFS 탐색을 수행해서 모양의 최대 넓이를 구하는 방식을 사용하면 시간 초과가 발생한다. 따라서 다음과 같은 순서대로 ..

문제https://www.acmicpc.net/problem/7569 여담토마토 문제와 거의 유사하다. 다른 점은 2차원에서 3차원으로 변경됐다는 것 정도? 그래서 문제 제목도 같나 보다. 토마토 문제를 풀고 바로 푸는 것이라 쉽게 풀 수 있었다. 풀이토마토들이 다 익는 최소 일수를 알고 싶은 것이므로 BFS 탐색을 수행하면 된다. 언급했듯이 이전에 풀었던 토마토 문제와 거의 유사하므로, 풀이 방법은 토마토 풀이 게시글을 참고하면 된다.  주의해야 할 점은 2차원이 아니라 3차원이라는 점이다. 따라서 상하좌우뿐만 아니라 위, 아래로도 BFS 탐색을 수행해야 한다. 코드import java.util.*;import java.io.*;public class Main { s..

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

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