본문 바로가기

dfs4

[JavaScript] 백준 30689번: 미로 보수 (DFS) 난이도 : 골드 3알고리즘 유형 : 깊이 우선 탐색문제 링크 : https://www.acmicpc.net/problem/30689  문제각 칸에 '상', '하', '좌', '우' 중 하나가 표시되어 있고 세로로 N칸, 가로로 M칸인 N×M 크기의 미로가 있다. 해당 칸으로 도착한 모든 사람은 미로에 표시된 방향으로 한 칸 이동한다. 이를 반복해 미로 밖으로 벗어나면 미로에서 탈출할 수 있다.영원히 탈출하지 못하는 상황을 막기 위해, 형진이는 미로를 보수하기로 했다.형진이는 미로에 원하는 만큼 점프대를 설치할 수 있다. 점프대를 설치하면 해당 위치에 도착한 사람들은 점프를 통해 바로 미로 밖으로 빠져나올 수 있다.점프대를 설치하기 위해서는 해당 칸의 지리적 조건 등을 고려해야 하므로, 어느 칸에 설치하냐.. 2024. 11. 10.
[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] 백준 2458번: 키 순서 (플로이드 워셜, DFS) 난이도 : 골드 4알고리즘 유형 : 플로이드 워셜, DFS문제 링크 : https://www.acmicpc.net/problem/2458  문제1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.입력첫째 줄에 학생들의 수 N (2 ≤ N ≤ 500)과 두 학생 키를 비교한 횟수 M (0 ≤ M ≤ N(N-1)/2)이 주어진다.다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 N보다 작거나 같은 서로 다른 양의 정수 a와 b가 주어진다. 이는 번호.. 2024. 11. 3.
[Algorithm] 백준 13460 구슬 탈출 2 (C++) https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 알고리즘 분류 구현 그래프 이론 그래프 탐색 너비 우선 탐색 시뮬레이션 문제 풀이 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나.. 2023. 5. 22.

티스토리툴바