목록dfs (22)
기록방
👉 문제링크🔸 문제 분석 🔸n x n 격자판에서 상하좌우로 움직였을 때 가장 긴 이동거리를 출력한다.이동 시 현재 위치 보다 큰 쪽으로만 이동할 수 있다.🔸 문제 풀이 🔸최장 이동 거리를 찾는 그래프 탐색 문제이고, 4방향 이동에 대한 정보를 따로 저장할 필요 없게 할 수 있도록 깊이 우선 탐색(DFS)를 사용한다.이동은 항상 격자판의 숫자가 큰 쪽으로 이동하므로, 특정 칸으로 진입하는 방향이 달라도 나가는 최적의 방법은 항상 같다. DP를 이용한다.이 원리를 이용해서 한 격자 칸에서 시작해서 최장 몇 길이까지 이동할 수 있는지 dp 배열에 저장해간다.이미 탐색했던 칸이라면, 재탐색 할 필요 없이 기존 최장값을 이용하면 된다.모든 칸에서 시작해보고 최대값을 구해 출력한다.🔸 코드 🔸impor..
👉 문제링크🔸 문제 분석 🔸N x N 지도에 2개 이상의 섬이 주어진다. 섬은 1로 상하좌우 연결된 덩어리이다.서로 다른 두 섬 사이에 다리 하나를 놓을 때, 다리의 길이의 최소값을 출력한다.🔸 문제 풀이 🔸단순한 그래프 탐색 문제이다.먼저 지도 상의 같은 섬 소속 1들을 묶어줄 필요가 있다.다리를 지을 때, 서로 다른 섬인지 알아야 하므로 섬 덩어리 별 다른 값을 넣는다.단순한 4방 탐색이므로, DFS나 BFS 상관 없이 사용하면 되는데, 여기서는 DFS로 통일해서 사용했다.섬 사이에 다리가 놓이는지 확인해야 한다.DFS로 한쪽 섬의 끝에서 다른 섬을 발견 할 때까지 탐색한다.한번 다리가 완성되면, 최소값으로 저장하고 백트래킹에 이용한다.🔸 코드 🔸import java.io.*;import..
👉 문제링크🔸 문제 분석 🔸T번의 테스트 케이스안에서 다음과 같은 입력이 주어진다.n명 (2~10만)의 학생 수가 주어지고, 다음 줄에 각 학생이 같이 팀을 하고 싶은 학생의 번호가 주어진다.자기 자신을 뽑거나, 팀을 하고싶은 학생들끼리 순환구조(서클)이 만들어지면 팀을 만들 수 있다.최종적으로 팀에 속하지 않은 학생의 수를 출력한다.🔸 문제 풀이 🔸제한시간 3초에 각 테스트 케이스의 n이 10만이기 때문에 O(n^2)의 알고리즘은 사용할 수 없다.팀이 만들어지는지 확인하기 위해 깊이 우선 탐색(DFS)를 사용한다.DFS의 경우의 수는 다음과 같다.1) 탐색하다가 시작 번호를 다시 찾음 : 탐색한 모든 학생들은 같은 팀2) 탐색하다가 중간 번호를 다시 찾음 : 중간 번호까지 팀이고, 시작 번호부..
👉 문제링크🔸 문제 분석 🔸바닷물과 맞닿은 빙하는 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 스도쿠 문제가 주어지면, 빈칸을 채워서 출력하는 문제이다. 🔸 문제 풀이 🔸 스도쿠 규칙에 따라 가로, 세로, 정사각형에 겹치는 숫자가 없도록 숫자를 채워가야 한다. 만약 숫자를 놓지 못하는 경우가 생기면, 직전에 놨던 숫자를 취소하고 다시 놓아 보아야 하기 때문에 백트래킹이 필요하다. 백트래킹에서 가로, 세로, 정사각형에 겹치는 숫자가 있는지에 대한 상태 정보도 필요하다. 숫자를 채워가며 마지막 칸까지 채우는데 성공하면, ..