문제 문제 바로가기> BOJ 13549번: 숨바꼭질 3 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 순간이동을 하는데는 시간이 소요되지 않으므로, 해당 위치에 최단 거리로 도착할 수 있도록, 시간을 업데이트해 줄 필요가 있다! #include #include #define MAX 100001 using namespace std; int N, K; int visit_time[MAX]; int main(){ ios_base::sync_with_stdio(0); cin.ti..

문제 문제 바로가기> BOJ 1697번: 숨바꼭질 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 기존의 방문한 지점을 제외하고, 이동할 수 있는 총 3가지 방법으로 이동하면서 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 찾아주면 된다! #include #include #define MAX 100001 using namespace std; int N, K; bool visited[MAX]; int main(){ ios_base::sync_with_stdio(0); cin.t..

문제 문제 바로가기> BOJ 2178번: 미로 탐색 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 BFS를 이용하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구할 수 있다! #include #include #define MAX 101 #define INF 987654321 using namespace std; int N, M; int maze[MAX][MAX]; int dist[MAX][MAX]; int dy[] = {-1,1,0,0}; int dx[] = {0,0,-1,1}; void input(){ cin >>..

문제 문제 바로가기> BOJ 1260번: DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 DFS와 BFS를 구현할 수 있는지를 보는 간단한 문제이다. 주의해야할 점은 "정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문"하기 때문에 미리 연결되는 node를 정렬해 두어야한다는 것이다! #include #include #include #include #define MAX 1001 using namespace std; int N, M, V; bo..

문제 문제 바로가기> BOJ 15591번: MooTube (Silver) 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 BFS를 이용해 탐색을 진행하면서, USADO(가중치)가 k이상인지 검사 해주었다! 전체 경로에서의 최소값이 최종 USADO가 되므로, 가는 경로에서 가중치가 한번이라도 k이상이면 그 동영상은 추천 받을 수 없다. #include #include #include #define MAX 5001 #define INF 1000000001 u..