본문 바로가기

BFS23

[백준] 2589번 보물 JAVA (자바) 풀이 문제 2589(BFS)  :  보물섬 지도의 각 칸은 육지(L)나 바다(W)로 표시    이동은 상하좌우로 이웃한 육지로만 가능, 한 칸 이동하는데 한 시간이 걸린다    보물은 육지 두 곳에 나뉘어 묻혀있고 두 곳을 이동하는 최단거리를 구해라    같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다  예) 보물은 아래 표시된 두 곳에 묻혀 있고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간  [입력] :  첫째 줄에는 지도의 가로, 로 ( 가로, 세로의 크기는 각각 50이하 ) :  다음 줄부터 L과 W로 표시된 보물 지도 (빈칸없이)   [출력] :  보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력     [문제접근] 1. 출력 배열 사용하지 말고 큐에다 넣어버리기co.. 2024. 6. 21.
[백준] 1697번 숨바꼭질 JAVA (자바) 풀이 문제 1697(BFS)  :  수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다  :  수빈이는 걷거나 순간이동을 할 수 있다     현위치가 X일 때     걷기 = 1초 후에 X-1 or X+1    순간이동 = 1초 후에 2*X  :  동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램  [입력] :  첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K   [출력] :  동생을 찾는 가장 빠른 시간을 출력     [문제접근] 1. 출력 배열 사용하지 말고 큐에다 넣어버리기count[] 배열보다 큐 자체에 넣는 것이 더 간단하다 q.add(new int{start,0}) 추천 2. for문 상하좌우 이동을 떠올릴.. 2024. 6. 20.
[백준] 24444번 알고리즘 수업 - 너비 우선 탐색 1 JAVA (자바) 풀이 문제 24444번 (bfs) :  N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)    정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다    정점 R에서 시작하여 노드의 방문 순서를 출력하자    인접 정점은 오름차순으로 방문한다bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점  for each v ∈ V - {R}  visited[v]    [입력] :  첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N) :  다음 M개 줄에 간선 정보 u v (가중치 1인 양방향 간선) (1 ≤ u  ≤ N, u ≠ v)    .. 2024. 6. 20.
[백준] 11060번 점프 점프 JAVA (자바) 풀이 문제 11060번 (bfs) :  1×N 크기의 미로 ( 1×1 크기의 칸으로 이루어져 있다)    i번째 칸에 쓰여 있는 수를 Ai  :  Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프가능    (예 : 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프가능)  :  현위치 = 미로의 가장 왼쪽 끝 / 가장 오른쪽 끝으로 가려고 할 때 최소 몇 번 점프를 해야하는지 구해라    (가장 오른쪽 끝으로 갈 수 없다면 -1을 출력)   [입력] :  첫째 줄에 N(1 ≤ N ≤ 1,000) :  둘째 줄에 Ai (0 ≤ Ai ≤ 100)  [출력] :  최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력     (갈 수 없다면 -1 출력) [설명] 1. 출.. 2024. 6. 19.
[백준] 14940번 쉬운 최단거리 JAVA (자바) 풀이 문제 14940번 (bfs) :  모든 지점에 대해서 목표지점까지의 거리를 구해라    :  가로와 세로로만 움직일 수 있다   [입력] :  첫째줄에 지도 세로 n, 가로 m ( 2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000 ) :  다음 n개의 줄에 m개의 숫자 ( 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점)  [출력] :  각 지점에서 목표지점까지의 거리를 출력     (원래 갈 수 없는 땅인 위치는 0 / 목표까지 도달할 수 없는 위치는 -1 출력) [설명] 1. 시작지점을 목표지점으로 잡기각 노드에서 목표지점으로 가는 것을 계산하려면 복잡목표지점부터 시작하면 가는 노드마다 거리가 기록됨 (간편) 2. 출력은 3가지값이 0이거나 2인 지점은 애초에 움직일 수 없기 때문에 0 .. 2024. 6. 18.
[백준] 18352번 특정 거리의 도시 찾기 JAVA (자바) 풀이 문제 18352번 (bfs) :  1번 ~ N번까지의 도시와 M개의 단방향 도로가 존재 (모든 도로의 거리는 1)  :  도시 X로부터 출발해 도달할 수 있는 도시 중에서, 최단 거리 K인 도시 모두 출력    자신에서 다시 자신으로 가는 최단 거리는 항상 0  예) N=4, K=2, X=1 최단 거리가 2인 도시는 4번 도시 뿐이다3은 2를 거쳐서 가면 거리가 2가 되지만 답은 최단거리를 구하는 것으로 3의 최단거리는 1-3이라 즉 1이 되기 때문에 답이 될 수 없다   [입력] :  첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X    (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N)  :  둘째 줄.. 2024. 6. 18.
[백준] 5014번 스타트링크 JAVA (자바) 풀이 문제 5014번 (bfs) :  건물 총 F층    스타트링크가 있는 곳의 위치는 G층    현위치 S층  :  엘리베이터는 버튼이 2개밖에 없다     U버튼은 위로, D버튼은 아래로 가는 버튼  :  G층에 도착하려면 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성    (만약, G층에 갈 수 없다면, "use the stairs"를 출력)   [입력] :  첫째 줄에 F, S, G, U, D (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000)   [출력] :  S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력     (갈 수 없다면, "use the stairs")  [설명] 1. count 가 아닌 arr 배열 이용하기 2. void가 아닌.. 2024. 6. 17.
[백준] 1389번 케빈 베이컨의 6단계 법칙 JAVA (자바) 풀이 문제 1389번 (bfs) :  모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다.    케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임  :  BOJ의 유저가 5명이고, 1 - 3, 1 - 4, 2 - 3, 3 - 4, 4 - 5 친구인 경우   1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다   케빈 베이컨의 수는 2+1+1+2 = 6   [입력] :  첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)    둘째 줄부터 M개의 줄에는 친구 관계  [출력] :  첫째 줄에 케빈 베이컨의 수가 가장 작은 사람을 출력 (여러 명일.. 2024. 6. 16.
[백준] 16953번 A → B JAVA (자바) 풀이 문제 16953번 (bfs):  정수 A를 B로 바꾸고 필요한 연산의 최솟값을 구해라 :  가능한 연산X 2수의 가장 오른쪽에 1 추가  [입력] :  첫째 줄에 A, B (1 ≤ A )   [출력] :  연산의 최솟값에 1을 더한 값을 출력 (만들 수 없는 경우 -1 출력)   [과정]  1. int 말고 long 사용뒷자리에 1을 추가하게 될 경우 숫자가 너무 커질 수 있다 2 - 1. count = 0라면while문 초입에서 ++하고 시작2 - 2. count = 1라면 while문 끝에서 ++하기 3. if문 조건계산한 숫자(p)가 b보다 클 경우, 작을 경우, 같을 경우 딱 세 가지이다if(p==b)랑 if(p>b) 만해주고 나머지는 p 4. void가 아닌 int 사용void를 사용하려면 re.. 2024. 6. 9.
[백준] 2178번 미로 탐색 JAVA (자바) 풀이 문제 2178(BFS)  : N×M크기 미로 101111101010101011111011: 1 = 이동할 수 있는 칸  0 = 이동할 수 없는 칸 : (1, 1) ~ (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구해라  서로 인접한 칸으로만 이동할 수 있고 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다  [입력] :  첫째 줄에 두 정수 N, M (2 ≤ N, M ≤ 100) :  다음 N개의 줄에는 M개의 정수로 미로   [출력] :  첫째 줄에 지나야 하는 최소의 칸 수를 출력     [문제접근] 좌표 사용 시 int[] 나 Point 사용→ int[] 배열을 사용Queue q = new LinkedList();q.add(new int[] {x,y});→ Point 사용import.. 2024. 6. 4.

티스토리툴바