목록BFS (29)
기록방
👉 문제링크🔸 문제 분석 🔸바닷물과 맞닿은 빙하는 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를 만들어 ..
👉 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔸 문제 분석 🔸 n x m 크기의 땅에 석유 덩어리들이 있다. 어느 지점에서 시추해야 가장 많은 석유를 시추하는지 구한다. 시추는 가장 위에서 수직으로 하는데, 시추기가 지나가는 석유 덩이리를 모두 시추할 수 있다. 🔸 문제 풀이 🔸 석유 덩어리를 처음 발견했을때 다음과 같이 처리한다. 석유 덩어리 번호를 붙인다. 해당 덩어리의 크기를 탐색해 파악하고, 번호에 맞게 크기를 저장해둔다. 마지막에 모든 지점에서 시추해보며, 시추 되는 석유량의 최대값을 반환한다. 🔸 코드 🔸 import java.u..
👉 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔸 문제 분석 🔸 n x m 맵에서 (0, 0) 부터 (n-1, m-1) 까지 이동하는데 최단거리를 반환한다. 만약 도달할 수 없다면 -1을 반환한다. 🔸 문제 풀이 🔸 전형적인 최단거리 문제로 너비 우선 탐색(BFS)로 풀이할 수 있다. 🔸 코드 🔸 import java.util.ArrayDeque; import java.util.Queue; class Solution { private static class Point { private int row, col; public Point(int r..
👉 문제링크 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 🔸 문제 분석 🔸 N * M 행렬 맵에서 (1, 1)부터 (N, M) 까지 이동하는 최단거리를 구한다. 인접한 상하좌우로 1칸씩 이동할 수 있다. 이동할 수 있는 칸은 0, 벽은 1로 표시되는데, 1번 벽을 부수고 이동할 수 있다. 행렬에서 최단거리를 구하는 문제이므로 BFS를 사용한다. 벽을 부수고 먼저 도착했었던 칸을 벽을 부수지 않고 도착했다면, 이어서 탐색해보아야 한다. 벽을 부수지않고 먼저 도착했던 칸이면 더 탐색해..