본문 바로가기

그래프 탐색

(6)
[백준 / BOJ] 1103 게임 문제 출처 : https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 형택이는 1~9까지의 숫자와 구멍이 있는 직사각형 보드에서 게임을 한다. 보드의 1,1위치에 동전을 하나 올려놓고, 동전을 다음과 같이 움직인다. - 동전이 놓인 위치에 있는 숫자만큼 위,아래,왼쪽,오른쪽 위치로 움직인다. (이 과정에서 구멍은 무시한다.) - 동전이 이동한 위치에 구멍이 있거나 동전이 보드 밖으로 나가면 게임이 종료된다. 형택이가 동전을 최대 몇번 움직일 수 있는지..
[백준 / BOJ] 15591 MooTube (Silver) 문제 출처 : https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 농부 존은 MooTube라는 동영상 공유 서비스를 만들었다. MooTube의 동영상들은 트리구조로 연결되어있고, 동영상 Vi를 볼때, Vi와 연결된 모든 동영상들중에 유사도가 Ki이상인 동영상들을 추천해준다. 이때, 동영상 Vi와 다른 동영상 Vj의 유사도는 Vi와 Vj 를 연결하는 경로의 최소 유사도이다. 소가 Vi동영상을 시청하..
[백준 / BOJ] 9376 탈옥 문제 출처 : https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 상근이는 감옥에서 죄수 두명을 탈옥시킬려고한다. N*M크기의 감옥이있고, 감옥은 # : 문 . : 빈 공간 $ : 죄수 로 구성되어있으며, 죄수는 항상 2명이다 (문이 있는곳은 지나가기위해 문을 열어야한다.) 모든 죄수를 탈출시키기 위해서 열어야 하는 문의 최솟값을 출력하는 문제였다. 풀이 다익스트라로 풀은 문제다. 처음 문제를보고 그냥 BFS를 돌리면 될것같다고 생각했는데, 한 죄수가 밖으로 ..
[백준 / BOJ] 13907 세금 문제 출처 : https://www.acmicpc.net/problem/13907 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 주언이는 두 도시를 오가며 무역을 한다. 이때, 도시의 통행료가 가장적은 길로 이동을 하려고한다. 도시들은 양방향으로 연결되어있으며 도로마다 통행료가 존재한다. 나라에서 도로의 통행료를 인상시킬려고한다. 통행료를 A만큼 인상시켰다면, 모든 도로의 통행료는 A만큼 증가한다. 주언이의 최초 최소통행료와, 세금이 오..
[백준 / BOJ] 16724 피리 부는 사나이 문제 출처 : www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net N*M지도가 있고, 그 위에 영과일 회원들이 있다. 지도의 각 칸에는 U,D,L,R 이 쓰여있는데, (순서대로 위, 아래, 왼쪽, 오른쪽) 성우가 피리를 불기 시작하면, 영과일 회원은 자기 발 아래의 방향에 맞게 이동한다. 재훈이는 영과일 회원의 안전을 위해 SAFE ZONE을 설치할려고한다. 영과일 회원이 어디에 있던지 항상 SAFE ZONE으로 들어갈수있도록..
[백준 / BOJ] 1005 ACM Craft 문제 출처 : www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 내가 원하는 건물을 건설할때 걸리는 최소 시간을 출력하는 문제다. 풀이 완전탐색으로 풀경우 N 3 이렇게 저장이 될건데, 4번건물을 짓기위해선 4번에 연결된 건물들을 모두 지어야한다(2번과 3번)라는 뜻 2. 끝까지 탐색하며 건물을 지을때마다 check배열을 업데이트 해준다. (바텀업으로 구현함) check배열을 업데이트할때, 전 위치의 건물들중 최댓값을 뽑아서 업데이트 해줘야함 이때 이미 ..