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

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/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/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/2583 여담좌표를 주의해야 한다.. 생각없이 풀다가 좌표를 잘못 설정해서 틀릴 뻔 했다. 칸을 기준으로 좌표를 생각하면 쉽게 풀 수 있다.  풀이직사각형이 그려진 위치를 1, 그려지지 않은 위치를 0으로 설정하여 map[x][y] == 0인 부분을 BFS 또는 DFS 방식으로 탐색하면 된다. 총 탐색 횟수 == BFS 또는 DFS 탐색 횟수각 영역의 넓이 == 탐색 시 좌표를 방문하는 횟수 다음과 같이 직사각형이 그려져있는 경우에는 (0, 0), (0, 4), (2, 4)에서 탐색을 시작하면 된다. 코드BFS 탐색import java.io.*;import java.util.*;public class Main { static int M, ..