기록방

👉 문제링크🔸 문제 분석 🔸바닷물과 맞닿은 빙하는 1년마다 상하좌우의 바닷물 수 만큼 줄어든다.빙하가 두 덩어리 이상으로 나뉘어지는 최소 시간을 출력한다.끝까지 두 덩어리가 되지 않으면 0을 출력한다.🔸 문제 풀이 🔸빙하가 녹는건 4방탐색을 하면 되고, 덩어리 확인은 그래프 탐색과 4방 탐색을 함꼐 하면 된다.여기서는 그래프 탐색 알고리즘으로 너비 우선 탐색 (BFS) 를 사용했다.🔸 코드 🔸import java.io.*;import java.util.ArrayDeque;import java.util.Queue;import java.util.StringTokenizer;public class Main { private static int N, M; private static int..

👉 문제링크 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 🔸 문제 분석 🔸 9x9 스도쿠 문제가 주어지면, 빈칸을 채워서 출력하는 문제이다. 🔸 문제 풀이 🔸 스도쿠 규칙에 따라 가로, 세로, 정사각형에 겹치는 숫자가 없도록 숫자를 채워가야 한다. 만약 숫자를 놓지 못하는 경우가 생기면, 직전에 놨던 숫자를 취소하고 다시 놓아 보아야 하기 때문에 백트래킹이 필요하다. 백트래킹에서 가로, 세로, 정사각형에 겹치는 숫자가 있는지에 대한 상태 정보도 필요하다. 숫자를 채워가며 마지막 칸까지 채우는데 성공하면, ..

👉 문제링크 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 🔸 문제 분석 🔸 무방향 그래프가 주어지면, 이분 그래프인지 아닌지 판별한다. 🔸 문제 풀이 🔸 그래프 탐색을 통해 각 노드가 서로 다른 집합에 속하는지 구분한다. DFS로 처음 방문한 노드에 한번은 A집합, 한번은 B집합으로 번갈아 가며 포함시킨다. 이미 방문한 노드인데, 같은 집합이면 이분 그래프가 아니다. 여러 개의 부분 그래프로 이루어 져있을 수 있으므로, 모든 노드에서 DFS를 시작해본다. 모든 탐색 이후 이분 그래프 판정 결과를 출력한다...

👉 문제링크 1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net 🔸 문제 분석 🔸 10 이하의 자연수 N이 주어지고, N-1 개의 재료 비율이 주어진다. 칵테일을 만드는데 필요한 각 재료의 최소 질량을 출력한다. 🔸 문제 풀이 🔸 기준값을 찾기 위해 입력된 p, q 비율들의 최소공배수를 구한다. N개의 재료와 N-1의 연결 정보는 N개의 노드와 N-1의 간선 정보이므로 트리 형태로 나타낼 수 있다. 한 노드에 값을 넣고 DFS로 인접한 노드를 탐색하며 입력된 비율로 각 노드의 질량 값을 만들어 간다. 모든 노드의..

👉 문제링크 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 🔸 문제 분석 🔸 N x M 모눈종이에 공기와 치즈가 0, 1 로 주어진다. 외부 공기와 2개 이상 맞닿은 치즈는 녹는다. 치즈가 모두 녹는데 걸리는 시간을 구한다. 🔸 문제 풀이 🔸 치즈 내부의 공기와 외부 공기를 분리해서 생각한다. 가장자리 면은 치즈를 두지 않는다고 문제에서 제한했으므로, (0,0)부터 그래프 탐색으로 인접한 0을 2로 바꾼다. 풀이에선 DFS를 사용했다. 공기와 맞닿은 치즈를 녹여 없앤다. 치즈가 녹은 자리는 공기..