문제 링크 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.ut...

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

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

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

문제 링크 1. 문제 풀이 바이러스를 노드, 연결 정보를 간선으로 간주한 그래프에서 1번 노드와 직간접적으로 연결된 다른 노드의 수를 구하는 문제로 생각할 수 있다. BFS 또는 DFS를 활용해서 방문한 노드의 수를 카운팅해주면 해결할 수 있다. 노드의 수가 크지 않아서 인접 행렬을 활용해서 구현했다. 2. 코드 1. BFS [J...

문제 링크 1. 문제 풀이 주어진 미로에서 이동할 수 있는 칸을 통해 $(1, 1)$ 에서 $(N, M)$ 까지 가는 최단거리를 구하는 문제로 사방 탐색과 BFS를 활용하면 간단하게 해결할 수 있다. 2차원 배열로 미로가 표현됐으므로 사방 탐색으로 다음에 이동할 후보지를 탐색하고, BFS는 큐의 크기만큼 탐색하면 등거리의 모든 후보를 탐색한...

문제 링크 1. 문제 풀이 주어진 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제로 정점 번호가 작은 것을 먼저 방문해야 한다. 인접 리스트를 활용했는데 이때 정점 번호가 작은 것을 먼저 방문할 수 있게 트리셋을 활용해서 정렬을 해줬다. 인접 리스트의 경우 양방향 연결을 해야함에 주의해야 한다. 2. 코드 1...