그래프_탐색

[C++] 백준 9466번 텀 프로젝트

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 그래프 탐색 문제. 그래프 내의 Cycle의 존재를 찾은 후에 해당 Cycle에서 몇 개의 노드가 존재하는 지 찾아서 해결하면 된다. 문제 풀이 나같은 경우에는 다음과 같은 방법으로 해결할 수 있었다. 그래프 탐색을 돌면서 각 수가 만나는 마지막 번호를 기록한다. 이 때, 다음 번호가 이미 방문된 번호라면 현재 번호를 Return한다. (해당 번호에서 Cycle이 발생했다는 뜻) 그 후 각 수가 만나는 마지막 번호들에 대해 그래프 탐색을 진행해서 노드의 개수를 찾는다..

[C++] 백준 19238번 스타트 택시

19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 수록 문제. 구현 + 시뮬레이션 + 그래프 탐색 알고리즘으로 풀 수 있다. 문제 해석 택시의 조건은 다음과 같다. 목적지에 도착 시, 연료가 충전된다. 연료가 바닥날 경우 업무가 끝난다. 택시는 빈 칸의 상, 하, 좌, 우로 이동하며 특정 위치에 최단 경로로만 이동한다. 연료는 이동 한 칸마다 1이 소모된다. 다른 조건들은 다음과 같다. M명의 승객을 태우는 것을 목표로 한다. 활동 영역은 ..

[C++] 백준 6593번 상범 빌딩

6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 삼차원 배열로 풀 수 있는 그래프 탐색 문제. 삼차원 배열 초기화, 출력만 잘 맞춰주면 쉽게 풀 수 있다. /* * 백준 6593번 상범 빌딩 * https://www.acmicpc.net/problem/6593 * 그래프 탐색 이론 - 너비 우선 탐색(BFS) */ #include #include #include using namespace std; struct Point { int l; int r; int c; }; Point startPoint; int buil..

[C++] 백준 13460번 구슬 탈출 2

13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 수록 문제. 구현 / 시뮬레이션 문제로, 설계를 잘하고 구현을 해야 풀 수 있는 문제. 문제 분석 문제의 조건은 다음과 같다. N*M 보드가 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬이 있다. 빨간 구슬을 구멍으로 빼야 한다. 파란 구슬은 구멍으로 빠지면 안된다. 구슬은 직접 움직일 수 없고 보드를 상, 하, 좌, 우로 기울여서 움직여야 한다. -> 이 때, 두 개..

[C++] 백준 1005번 탈출

1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 그래프 탐색과 DP를 통해 해결할 수 있는 문제. 특정 건물을 짓기 위해 어떻게 빨리 지을 수 있는 지 알아내는 알고리즘을 작성하는 문제였다. 알고리즘 분류를 보니, 위상 정렬이라는 알고리즘이 있었는데 해당 알고리즘에 대해서는 내가 아는 바가 없었지만 풀 수는 있었다. 문제 풀이 예시 이미지를 통해 문제를 해석해 보았다. 4번 건물을 짓기 위해서는 10초의 시간이 필요하며, 2번과 3번의 건물이 지어져 있어야 한다. 2번 건물을 짓기 위해서는 1초의 시간이..

[C++] 백준 3055번 탈출

3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 4179번 불! 과 같은문제 [C++] 백준 4179번 불! 그래프 탐색 문제. 최근에 이런 비슷한 문제인 3055번 탈출이라는 문제를 풀다가 실패했었다. 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 kimyunseok.tistory.com 그래프 탐색을 두 종류로 나누어서 진행해주면 된다. 저 때 풀이와 완전 다르게 풀었다. 문제 풀이 다음과 같은 조건이 있다. 마법을 부려 숲에 홍수를 낸다. 1마리인 도치가 비버굴..

[C++] 백준 16562번 친구비

16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 그래프 탐색 문제. 그래프가 여러개 존재한다고 생각하고 각 그래프에서 최소값을 찾으면 되는 문제다. 문제풀이 각 친구마다 친구비가 드는데, 친구의 친구도 친구가 된다. 즉, 이는 친구 관계가 edge가 되고 학생은 vertex가 된다고 해석했다. 그 후, 연결된 Vertex들 끼리 그래프 탐색을 한 후에 최소비용을 찾으면 된다. 어차피 최소비용의 학생하고만 친구를 하면 나머지는 자동으로 친구가 될..

[C++] 백준 1043번 거짓말

1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 그래프 탐색 문제. 그래프 탐색이라는 점을 발견한다면 어렵지 않게 풀 수 있다. 변수를 잘못 재사용해서 몇 번 틀려버려서 아쉬운 문제. 문제 풀이 문제는 다음과 같은 조건들이 있다. 지민이는 사실 혹은 과장(거짓말)을 말한다. 최초 사실을 아는 사람이 K명이라 할 때, 이 사람들에게는 사실만 말해야 한다. 사실을 들은 사람이 있다면 이 사람들이 있는 파티에서는 사실만 말해야 한다. 즉, 사실 & 과장 둘 다 들을 수는 없다. 따라서 사실을 아는 사람이 있는 파티를 먼저 제..

[C++] 백준 2589번 보물섬

그래프 탐색 문제. 오랜만에 풀어보는 알고리즘 문제라 그런지 머리가 잘 안 돌아갔지만 그래프 탐색이란 것을 알고 쉽게 풀 수 있었다. 문제풀이 땅 - 땅으로 이동하는 거리중 가장 긴 거리를 찾으면 된다. 돌아가면 안되고 최단거리 기준이므로 DFS는 안되고 BFS로 탐색해야한다. 이 기준대로만 구현하면 쉽게 풀 수 있다. /* * 백준 2589번 보물섬 * https://www.acmicpc.net/problem/2589 * 그래프 탐색 이론 - 너비 우선 탐색, 브루트 포스 */ #include #include #include #include using namespace std; int height, width; char board[51][51]; bool visit[51][51]; vector visi..

[C++] 백준 2638번 치즈

2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 구현 / 시뮬레이션 / 그래프 탐색 문제. 문제에서 구현하라는 대로 구현해서 풀면된다. 제출하고 시간이 44ms가 나왔는데, 다른 사람들은 보통 12 ~ 20ms가 나온 것 같았다. 유의미한 차이는 아니라서 일단은 그냥 넘어갔다. 문제풀이 문제의 조건들은 다음과 같다. 격자의 가장자리들에는 치즈가 존재하지 않는다. 한 시간마다 외부공기와 동, 서, 남, 북 중 두 방향 이상 외부공기와 접한 치즈는 녹는다. 치즈로 둘러쌓인 공간은 외부 공간으로 치지 ..