문제 링크 1. 아이디어 어떤 지역의 높이 정보가 주어졌을 때, 안전 영역의 최대 개수를 구하는 문제로 비의 양에 따른 안전 영역을 전부 구해보면 해결할 수 있다. 안전 영역은 플러드 필을 활용해서 개수를 구할 수 있으며 높이 정보가 1에서 100 사이의 자연수이므로 비의 양을 0부터 99까지 높여가며 탐색해서 최댓값을 갱신해나가면 된다. ...

문제 링크 1. 아이디어 도화지에 있는 그림의 수와 가장 넓은 그림의 넓이를 구하는 문제로 도화지의 각 칸에 대해 그림의 일부이면 BFS나, DFS를 통해 넓이를 구하고 방문 체크를 하면 간단하게 해결할 수 있다. 2. 코드 1. BFS [Java] import java.io.*; import java.util.*; publi...

문제 링크 1. 아이디어 적록색약이 아닌 사람은 RGB를 모두 구분하고 적록색약인 사람은 R과 G를 동일하게 볼 때 구역의 수를 구하는 문제로 적록색약이 아닌 사람이면 두 색상이 동일한지를 반환하고, 적록색약인 사람이면 두 색상 중 하나가 B일 때는 두 색상이 동일한지, 아니면 true를 반환하는 isSame 함수를 탐색 조건으로 활용했다....

문제 링크 1. 문제 풀이 지도에 무인도들이 주어져 있고 각 무인도는 섬의 모든 숫자의 합으로 머물 수 있는 날이 정해질 때 지도에서 각 섬별로 머물 수 있는 날을 오름차순으로 구해야 하는 문제다. BFS를 활용해서 지도를 순회하며 섬을 발견하면 해당 섬에 머물 수 있는 날을 계산하며 섬을 방문 처리하는 방식으로 해결했다. 2. 코드 ...

1. 영속성 컨텍스트 1 JPA에서 가장 중요한 것을 2가지 뽑는다면 객체와 관계형 DB 매핑하기와 영속성 컨텍스트이다. 지난 시간에도 잠깐 나왔는데 엔티티 매니저 팩토리는 클라이언트의 요청마다 엔티티 매니저를 생성하며 엔티티 매니저가 DB 커넥션을 사용해서 DB에 쿼리를 보내는 구조다. 영속성 컨텍스트는 엔티티를 영구 저장하는 환경이...

문제 링크 1. 문제 풀이 주어진 D, S, L, R 연산을 활용해서 $A$ 를 $B$ 로 바꾸는 최소 명령어 나열을 구하는 문제로 BFS와 역추적을 활용하면 해결할 수 있다. 먼저 주어진 명령어를 처리할 수 있어야 하는데 임의의 수 $n$ 에 대해 아래와 같이 각 명령어가 적용된 결과를 구할 수 있다. D: $(n \times 2...

문제 링크 1. 아이디어 나이트의 이동으로 목적지에 갈 수 있는 최소 횟수를 구하는 문제로 최단거리 BFS를 활용하면 해결할 수 있다. 일반적인 격자 그래프에서의 사방 탐색이 아닌 나이트의 이동 방법에 맞춘 팔방 탐색을 활용하면 된다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.uti...

문제 링크 1. 아이디어 3차원 빌딩에서 목적지에 도달할 수 있는지, 도달할 수 있다면 몇 분이 걸리는지 구하는 문제로 3차원 탐색을 위한 육방 탐색을 활용한 BFS로 간단하게 해결할 수 있다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*; public class Main...

문제 링크 1. 문제 풀이 다이나믹 프로그래밍을 활용해도 되고 BFS를 활용해도 해결할 수 있다. 다이나믹 프로그래밍의 경우 dp 테이블에서 인덱스를 숫자 $i$, 값을 $x$ 에서 해당 숫자로 변환하는데 필요한 최소 쵯수를 기록하면 된다. 초기 무한대로 초기화한 후 $dp[x] = 0$ 으로 초기화를 해준다. 이후 $x$ 부터 $n$ 을...

문제 링크 1. 아이디어 1층 빌딩의 정보가 주어져 있을 때 훔쳐올 수 있는 문서의 최대 개수를 구하는 문제다. BFS를 활용하면 해결할 수 있는데 먼저 빌딩 외부에서 빌딩의 경계 중 통과할 수 있는 곳을 통해 진입한다는 점에서 빌딩 외부에 빈 공간으로 이루어진 패딩을 한 칸 주고 $(0, 0)$ 에서 탐색을 시작해서 시작점을 찾는 로직을 ...