본문 바로가기

BFS4

[JavaScript] 백준 2206번: 벽 부수고 이동하기 문제 정보난이도 : 골드 3알고리즘 유형 : BFS문제 링크 : https://www.acmicpc.net/problem/2206 문제 풀이(1, 1)에서 (N, M)까지 이동하는 최단 경로를 찾는 문제다. 맵에는 벽이 있지만, 단 한 번만 벽을 부술 수 있는 능력이 있다. 모든 인접한 칸으로의 이동 비용은 동일하기 때문에 BFS를 활용하여 최단 경로를 구할 수 있다. 이 문제에는 벽을 한 번 부술 수 있다는 조건이 있다.따라서 동일한 위치에 도달하더라도 아래의 2가지 상태가 나올 수 있다.벽을 한 번도 부수지 않은 상태로 도달한 경우이미 벽을 한 번 부수고 도달한 경우앞으로의 경로 선택에 영향을 미치기 때문에, 이 두 상태는 서로 다른 상태로 관리해야 한다. 일반적인 BFS에서는 방문 여부를 bool.. 2025. 5. 12.
[JavaScript] 백준 2665번: 미로 만들기 (BFS) 난이도 : 골드 4알고리즘 유형 : 너비 우선 탐색문제 링크 : https://www.acmicpc.net/problem/2665  문제n×n 바둑판 모양으로 총 $n^2$개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 시작방에서 끝 방으로 갈 수가 없는 경우가 있다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다. 검은 방에서 흰 방으로 바꾸어야 할 최소.. 2024. 11. 12.
[JavaScript] 백준 1240번: 노드사이의 거리 (DFS, BFS) 난이도 : 골드 5알고리즘 유형 : 깊이 우선 탐색, 너비 우선 탐색문제 링크 : https://www.acmicpc.net/problem/1240  문제 N개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.입력첫째 줄에 노드의 개수 N과 거리를 알고 싶은 노드 쌍의 개수 M이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.출력 M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.  풀이 과정메인 생각 : 시작 노드 부터 DFS 또는 BFS를 이용해 트리를 탐색하며 도착 노드까지의 거리를 측정한다.로직 과정입력 정리N - 1개의 연관.. 2024. 11. 3.
[JavaScript] 백준 1389번: 케빈 베이컨의 6단계 법칙 (플로이드 워셜, BFS) 난이도 : 실버 1알고리즘 유형 : 플로이드 워셜, 너비 우선 탐색문제 링크 : https://www.acmicpc.net/problem/1389  문제케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.예를 들어, 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,0.. 2024. 10. 30.

티스토리툴바