기록방

👉 문제링크🔸 문제 분석 🔸바닷물과 맞닿은 빙하는 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..

👉 문제링크 14499번: 주사위 굴리기첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지www.acmicpc.net🔸 문제 분석 🔸N x M 지도에서 정육면체 주사위를 굴려가며, 주사위 윗면의 숫자를 출력한다.주사위가 이동했을 때 다음과 같은 숫자 변화가 있다.이동한 지도의 칸의 숫자가 0이면, 맞닿아 있는 주사위 아랫면의 숫자가 지도로 복사된다.이동한 지도의 칸의 숫자가 0이 아니면, 지도의 숫자가 주사위 아랫면으로 복사된다.🔸 문제 풀이 🔸주사위의 회전에 따른 숫자 이동을 구현한다.지도상의 ..

👉 문제링크 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🔸 문제 분석 🔸 N개의 도시 중 M개의 도시를 여행하고자 한다. 경로가 있어서 여행이 가능하면 YES, 불가능하면 NO를 출력한다. 🔸 문제 풀이 🔸 여행 하고자 하는 M개의 도시 간에 경로가 있는지 파악하는 쉬운 방법은 같은 집합에 있는지 확인하는 것이다. 분리 집합(Disjoint Set)으로 N개의 도시들의 집합을 나눈다. 여행 계획상의 도시들이 같은 집합에 있으면 경로가 존재한다는 뜻이다. 분리 집합이 아니라 BFS나 DFS로 Brute F..

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

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