목록BFS (32)
기록방
👉 문제링크🔸 문제 분석 🔸N x M 직사각형 땅에 수영장을 만든다. 격자 속 숫자가 해당 땅의 높이이다.물을 채워야 하는데, 물은 상하좌우 높은 곳에서 낮은 곳으로만 흐르고 격자 밖으로는 무한정 흘러나가 버린다.채울 수 있는 물의 양의 최대값을 출력한다.🔸 문제 풀이 🔸상하좌우 인접 땅으로 흐르는 물의 이동을 구현하기 위해서 BFS를 사용한다.외각에 붙은 땅은 물이 고일 수 없으므로, 역방향 BFS를 통해 이어진 땅들을 모두 체크한다.물이 고일 수 있는 땅들에 물을 채우고 총합을 출력한다.물 높이의 최대값은 2가지 기준을 유의해서 정한다.해당 높이보다 높아지면 물이 흘러나가버리는 경우 : 최대값의 인덱스가 체크된 경우흘러나가지는 않지만, 땅이 높아서 조금 더 높이 물이 고이는 경우 : 최대값의..
👉 문제링크🔸 문제 분석 🔸R x C 격자판에서 지훈이의 위치와 불들의 위치가 주어진다.지훈이는 1분에 상하좌우 4방향으로 이동할 수 있고, 불도 1분에 4방향으로 확산된다.격자판의 가장자리로 가면 미로를 탈출 할 수 있다.지훈이가 불을 피해 미로를 탈출하기 위한 최단시간을 출력한다.만약 탈출하지 못한다면 "IMPOSSIBLE"을 출력한다.🔸 문제 풀이 🔸격자판에서 최단 거리를 구하는 단순 BFS 문제이다. 하지만 지훈이의 이동과 불의 확산 모두 고려해야 한다.큐를 이용한 BFS 구현에서 큐 사이즈만큼 반복해서 '1분'의 움직임을 제한해야 한다.지훈이의 위치는 맵에 그리지 않고 큐에만 넣고, 불은 맵에 'F'로 표시해 간다.지훈이는 불로 이동할 수 없을 뿐만 아니라, 큐에서 꺼냈을 때 현재 위치..
👉 문제링크🔸 문제 분석 🔸N x N 지도에 2개 이상의 섬이 주어진다. 섬은 1로 상하좌우 연결된 덩어리이다.서로 다른 두 섬 사이에 다리 하나를 놓을 때, 다리의 길이의 최소값을 출력한다.🔸 문제 풀이 🔸단순한 그래프 탐색 문제이다.먼저 지도 상의 같은 섬 소속 1들을 묶어줄 필요가 있다.다리를 지을 때, 서로 다른 섬인지 알아야 하므로 섬 덩어리 별 다른 값을 넣는다.단순한 4방 탐색이므로, DFS나 BFS 상관 없이 사용하면 되는데, 여기서는 DFS로 통일해서 사용했다.섬 사이에 다리가 놓이는지 확인해야 한다.DFS로 한쪽 섬의 끝에서 다른 섬을 발견 할 때까지 탐색한다.한번 다리가 완성되면, 최소값으로 저장하고 백트래킹에 이용한다.🔸 코드 🔸import java.io.*;import..
👉 문제링크🔸 문제 분석 🔸바닷물과 맞닿은 빙하는 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..
👉 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔸 문제 분석 🔸 정수 x, y, n이 입력된다. x를 3가지 연산 (+n, x2, x3) 으로 y를 만드는 최소 연산 횟수를 반환한다. y를만들 수 없으면 -1을 반환한다. 🔸 문제 풀이 🔸 BFS와 DP로 풀이할 수 있다. BFS는 각 인덱스를 처음 방문했으면 다음 3가지 연산을 수행해서 y를 찾아가는데, y를 초과하거나 이미 방문 했으면 제외한다. DP는 x부터 y까지 인덱스를 늘려가며 계산하는데, 처음 방문이면 현재 값을 넣고 이미 값이 있으면 더 작은 값을 선택하는 방식으로 y를 만들어 ..