BFS
[BOJ / 플러드필 BFS] 2638 치즈
https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 2638 치즈 알고리즘 : 플러드필 / BFS 바깥공기와 치즈, 안쪽 공기를 나누어 표기하고 첫 큐를 이용해 바깥공기를 처리, 공기에 맡닿은 치즈를 골라주고, 두번째 큐를 이용하여 다음 시간대에 녹을 치즈를 골라줍니다. 그렇게 골라서 만약 바깥공기와 안쪽 공기가 닿을 경우 첫 큐를 이용하여 처음과 같은 처리를 다시 이용해 주되, 메모이제이션을 통해 중복된 연산을 하지 않도록 합니다. ..
[BOJ / 메모이제이션 BFS] 2157 여행
https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 2157 여행 알고리즘 : 메모이제이션 / BFS 기본적인 메모이제이션을 이용한 BFS 풀이입니다. 인접리스트를 이용하여 각 도시간 항로를 만드는데 도착지가 출발지보다 작은 경우는 추가하지 않습니다. (시간 절약) 메모이제이션 테이블은 DP[A][B]=K를 - A : 현재까지 들린 도시의 수 - B : 현재 도시 번호 - K : 최대 ..
[BOJ / 비트마스크 DP] 1102 발전소
www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이 www.acmicpc.net 1102 발전소 알고리즘 : 비트마스크 DP / BFS 비트마스크를 DP배열의 iterator로 사용하는 문제입니다. dp를 이용해 현재 적용중인 상태에서 이미 들린 상태이거나 이미 결과값을 초과한 경우 가지치기를 하면 됩니다. 문제에서 해결이 안되는 경우에는 -1을 출력하라고 했으나, 모든 발전소는 다른 모든 발전소를 킬 수 있으므로 즉, 키는 비용에 음수값이 주어지는 경우가 없으므로 -1을 출력하는 경우는 모든 발전소가..