백준 5214 https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 풀이 전 나의 생각 하이퍼튜브의 정보가 주어졌을 때, 1번역에서 N번역으로 갈 수 있는 최소 역의 수를 구해야 한다. 조건 - (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) - K는 서로 연결하는 역의 번호 과정 처음 문제를 보면 서로 역을 연결하고 있다는 키워드를 볼 수 있다. 그래서 자연스럽게 그래프를 떠올릴 수 있고 어떻게든 주어진 역..
알고리즘 및 자료구조/그래프
백준 1043 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 전 나의 생각 이야기의 진실을 알고 있는 사람과 각 파티의 사람 정보가 주어질 때 지민이가 과장되게 말할 수 있는 파티의 수를 구해야 한다. 조건 - N, M은 50 이하의 자연수 - 진실을 아는 사람의 수는 0 이상 50 이하의 정수 - 파티마다 오는 사람의 수는 1 이상 50 이하의 정수 과정 진실을 알고 있는 사람이 3이고 파티에 같이있는 사람이 4라면 4는 이야기가 진실이라는 것을..
백준 6118 https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 M; //헛간의 정보 저장(양방향) for (int i = 0; i > A_i >> B_i; link[A_i].push_back(B_i); link[B_i].push_back(A_i); } //수혀니는 헛간 1번에 위치 bfs(1); //구해 놓은 헛간 거리의 최대값 for (int i = 1; i < N; i++) { if (ans < hide_dist[i]) { ans = hide_dist[i]; } ..
백준 1325 https://www.acmicpc.net/problem/1325 B의 형태로 관계 정보를 저장하면 A가 B를 신뢰하며 A가 B를 공격하기 때문에 이를 유의하며 정보를 저장해야 한다. 두 번째로 A가 B를 신뢰한다고 했을 때, B도 A를 신뢰할 수 있다. 따라서 방향성이 있는 그래프지만 전의 노드를 재탐색할 경우를 대비해 방문 표시를 해줘야한다. 이러한 점을 생각하며 DFS, BFS를 이용한 탐색을 진행할 때 마다 해킹할 수 있는 컴퓨터의 개수를 증가시켜 주면 된다. 풀이 #include #include #include #include #include #include #include #include #include #include using namespace std; vectorlink(1..
백준 1389 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이 전 나의 생각 친구 관계의 정보가 주어질 때, 케빈 베이컨의 수가 가장 작은 사람을 구해야한다. 케빈 베이컨이란 현재 선택된 사람으로 부터 어떤 친구까지 갈 수 있는 단계의 총합을 말한다. 조건 -N (2 ≤ N ≤ 100) -M (1 ≤ M ≤ 5,000) 과정 문제 설명은 정말 길지만 결국, 문제에서 요구하는 건 친구 관계 그..
백준 2660 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 풀이 전 나의 생각 월드컵 축구의 응원을 위한 모임의 친구 관계가 그래프의 형태로 주어진다. 어떤 회원이 다른 모든 회원과 친구, 친구의 친구, 친구의 친구의 친구... 의 조건에 따라 점수가 주어지질 때 회장이 될 수 있는 후보 점수와 후보의 수, 후보를 구해야한다. 조건 - 회원의 수는 50명을 넘지 않는다. - 마지막 줄에는 -1이 두 개 들어있다. 과정 이 문제는 결국 주어진..
백푼 11403 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 전 나의 생각 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 갈 수 있는지 확인해야 한다. 조건 - N (1 ≤ N ≤ 100) 과정 문제에서 요구하는 사항을 보면 i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하라고 한다. 이 말은 결국 i에서 j로 갈 수 있는지 없는지 물어보는 것이다. 예를 들어, 노드 1에서 노드 3으로 갈 수 있는지 확인하려고..
백준 5567 https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 풀이 전 나의 생각 상근이의 친구와 친구의 친구를 결혼식에 초대하기로 했을 때, 동기들의 친구 리스트를 기준으로 초대할 사람의 수를 구해야한다. 조건 - n (2 ≤ n ≤ 500) - m (1 ≤ m ≤ 10000) - (1 ≤ ai < bi ≤ n) 과정 상근이의 동기 친구 관계 리스트는 그래프 형태로 주어지기 때문에 그래프를 상근이의 친구, 친구의 친구까지 DFS..
