https://www.acmicpc.net/problem/23059 🏗️ 설계 더 이상 아이템을 구매하기 위해서 필요한 이전 아이템이 없을 경우 아이템을 구매할 수 있기 때문에 위상 정렬을 떠올려서 문제를 풀었습니다. Map에 이 아이템을 구매해야만 구매할 수 있는 아이템들을 nextItems List에, 이 아이템을 구매하기 위해 필요한 아이템들의 남은 개수를 needNum에 저장하여 needNum이 0이 되었을 때 해당 아이템의 nextItems List의 아이템들의 needNum을 1씩 감소시켜주고, 아이템을 출력하는 방식으로 문제를 풀이하였습니다. 📋 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.Input..
알고리즘 문제풀이/백준
https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 🏗️ 설계 초기 Board에서 0이 사방으로 움직일 수 있는 위치를 찾아 해당 위치의 값과 Swap 하여 새로운 Board를 생성합니다. 새롭게 생성된 Board를 HashSet에 들어가 있는 값인지 확인한 이후 들어있지 않은 값이라면 Queue와 HashSet에 add하며 BFS를 수행하도록 합니다. 최초로 타겟 표가 나온 값까지 가는 횟수를 리턴하고, Queue가 빌 때까지 타겟 표가 나오지 않았다면 -1를 리턴하는 방식으로 풀이하였습니다. 📋 코드 import java..
https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 🏗️ 설계 처음에는 BFS를 재귀적으로 호출 하면서 키를 획득할 수 있는 지점부터 다시 BFS를 수행하며 최단 거리를 갱신해 나가는 방식으로 풀이하려고 하였습니다. 하지만 위 방법은 (키의 갯수)! 번 만큼의 BFS를 수행하게 되므로 계속해서 메모리 초과가 발생하였습니다. 이 방법을 해결하기 위해서 예전에 “말이 되고 싶은 원숭이” 문제에서 풀었던 방법과 비슷하게 k..
https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 🏗️ 설계 초기 입력받은 스도쿠 판에서 빈 칸의 좌표를 ArrayList에 저장해 둔 이후 빈 칸의 좌표에 1~9까지 차례대로 넣어봅니다. 넣어본 값이 해당 값에 유효한지 여부를 판단한 후 유효하다면 다음 칸으로, 유효하지 않다면 백트래킹 기법으로 가지치기 하는 방식으로 풀이하였습니다. 유효 여부 판단 방법 같은 열에 동일한 값이 존재하지 않는지 같은 행에 동일한 값이 존재하지 않는지 3 *..
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 🏗️ 설계 조합을 이용해서 빈칸 중 세 개를 고를 수 있는 모든 경우의 수를 탐색합니다. 각 빈칸을 고른 후 벽을 세운 결과로 BFS를 이용하여 바이러스가 퍼질 수 있는 위치를 모두 바이러스로 덮습니다. 이후 남은 ‘0’인 칸을 카운트하여 가장 많은 0이 남는 수를 저장하여 출력합니다. 📋 코드 import java.io.BufferedReader; import java.io.IOException; impor..
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 🏗️ 설계 dijkstra 알고리즘을 이용하여, 최소가 되는 거리들을 PriorityQueue에서 꺼낸 후 최소 거리를 갱신해 나가는 방식으로 풀이하였습니다. 📋 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQ..
https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 🏗️ 설계 모든 점들에 대해서 한번씩 시작 지점으로 잡고 BFS를 이용하여 모든 점들을 방문할 수 있는지 여부를 확인하고, 모든 점들을 방문할 수 있을 경우에 minCost 값을 갱신하는 방법으로 풀이하였습니다. 📋 코드 import java.io.BufferedReader; import java.io.IOException; import java.io...
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 🏗️ 설계 현재 칸으로 올 때 가로 파이프로 오는지, 세로 파이프로 오는지, 대각선 파이프로 오는지를 구분하여 dp 배열을 3개로 만들었습니다. 가로로 오는 경우는 이전 칸에 대각선, 가로로 오는 경우 세로로 오는 경우는 이전 칸에 대각선, 세로로 오는 경우 대각선으로 오는 경우는 이전 칸에 대각선, 가로, 세로로 오는 경우 이렇게 세 가지로 케이스를 분류하여 DP를 이용..
