기록방

👉 문제링크 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 🔸 문제 분석 🔸 H x W 격자 판에 치즈가 있다. 치즈는 가장자리에 놓이지 않는다. 공기와 접촉한 치즈는 한 시간 뒤 녹아 없어진다. 치즈 안에는 1개 이상의 구멍이 있다. 구멍 안의 공기는 외부 공기와 접촉하기 전까진 치즈를 녹이지 않는다. 치즈가 모두 녹아 없어지는 데 까지 걸린 시간과 직전 치즈 개수를 출력한다. 그래프 탐색이므로 BFS혹은 DFS를 사용한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOE..

👉 문제링크 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 🔸 문제 분석 🔸 H x W 격자 판에서 왼쪽 위 끝 부터 오른쪽 아래 끝 까지 가는 동작의 최소값을 출력한다. 원숭이의 움직임 : 인접 4칸으로 이동 가능 말의 움직임 : k번 만큼 이동 가능 BFS로 2가지 풀이를 할 수 있다. 말 이동 횟수를 적게 쓸 수록 좋다.(그리디) 3중 배열로 방문을 체크한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; impor..

👉 문제링크 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 🔸 문제 분석 🔸 N개의 도시에서 모든 도시를 방문하고 마지막에 출발지로 돌아오는 여행 경로 중 가장 적은 비용을 출력한다. 재귀와 백트래킹을 통해 구현한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public..

👉 문제링크 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 🔸 문제 분석 🔸 N개의 서쪽 지점에서 M개의 오른쪽 지점으로 다리를 연결 하는 경우의 수를 구한다. 다리는 서로 겹칠 수 없다. 한 지점은 하나의 다리만 놓일 수 있다. 조합으로 접근할 수 있다. N

👉 문제링크 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 🔸 문제 분석 🔸 정수 N을 1로 만드는 가장 적은 연산 수를 출력한다. 연산은 -1, /3, /2 세 가지가 있다. DP, DFS, BFS 모두 풀이 가능하다. 🔸 DP 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { // Input BufferedReader br = new BufferedReader..