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

문제https://www.acmicpc.net/problem/1937 풀이n이 500이라 모든 위치에서 DFS를 돌려 최대 길이를 구하면 시간 초과가 발생한다. 따라서 DP(메모이제이션)를 함께 사용해야 한다. 대나무 숲 정보를 저장하기 위한 배열 외에도 dp 배열을 하나 더 선언해서 각 위치에서 이동할 수 있는 칸의 최대 개수를 기록해야 한다. (+ 방문 확인 기능) 시간을 줄이기 위해서는 이미 탐색했던 곳을 다시 확인하지 않아야 하므로, dp 배열에 값이 이미 기록되어 있다면 그 값을 바로 반환하면 된다. 그렇지 않다면 현재 위치에서 네 방향을 모두 탐색해야 한다. 이때, dfs 메서드를 호출해서 다음 칸에서 이동할 수 있는 칸의 최대 개수를 구해야 한다. 그리고 그 값을 현재 위치의 dp 배열에 더..

문제 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 탐색을 수행해서 다른 섬에 도착하는 경우에만 최단 거리를 갱신하면..

문제https://www.acmicpc.net/problem/9466 여담처음에 BFS 방식으로 사이클을 찾으려고 했다가 계속 시간초과가 발생했다. 찾아보니 사이클을 판별할 때는 DFS 탐색을 사용해야 한다고 한다.. 그래프 탐색으로 사이클을 찾을 때는 DFS 탐색 & 배열 2개를 기억하자! 풀이프로젝트를 함께 하고 싶은 학생을 선택한 것을 연결했을 때, 사이클이 발생하면 하나의 팀을 구성할 수 있다.1번 학생이 2번 선택, 2번 학생이 3번 선택1 → 2 → 3 ... (단방향) 사이클을 탐지하기 위해 DFS 탐색 시 방문 여부를 기록하는 visited 배열과 팀 구성 여부를 기록하는 check 배열, 즉 총 2개의 배열을 생성해야 한다. 우선 선택의 결과를 입력받고 팀 구성이 완료되지 않은 학생만 D..

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/2638 여담일루미네이션 문제와 치즈 문제와 비슷하다고 느꼈다. 그래서 "중간에 공간이 뻥 뚫린 것을 제외하고 탐색할 때는 역으로 생각을 하자!"라고 외웠던 것을 바탕으로 문제를 풀었다. 바깥에서부터 탐색을 할 수도 있다는 것을 기억하자! 풀이이 문제는 일루미네이션 문제와 치즈 문제와 푸는 방식이 동일하다. 즉, 역으로 생각해서 밖에서부터 탐색을 수행해야 한다. 치즈의 4변 중에서 적어도 2변 이상이 공기와 접촉하면 해당 치즈는 녹게 된다. 이때, 치즈 내부에 있는 공간은 외부와 접촉하지 않으며 녹지 않는다.  즉, 치즈 외부에 있는 공기와 접촉할 때만 치즈가 녹는다. 따라서 치즈(=회색 부분)를 탐색하는 것이 아니라, 치즈가 없는 부분(=흰색..

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