전체 글

백준 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..

백준 2606 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 풀이 전 나의 생각 컴퓨터 네트워크의 연결 구조가 그래프의 형태로 주어진다. 이때, 첫 번째 컴퓨터에 웜 바이러스가 퍼졌을 때 최대 몇 대의 컴퓨터 까지 퍼질 수 있는지 구해야 한다. 조건 - 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 과정 웜 바이러스는 무조건 1부터 시작하고, 컴퓨터 1번과 연결된 컴퓨터들을 탐색하려면 그래프의 형태로..

백준 2533 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 풀이 전 나의 생각 친구 관계 트리가 주어졌을 때, 최소 얼리 어답터의 수를 구해야 한다. 현재 선택한 친구가 얼리 어답터인 경우, 연결된 친구들은 모두 일반인이거나 얼리 어답터일 수 있다. 현재 선택한 친구가 일반인일 경우, 연결된 친구들은 모두 얼리 어답터가 되어야 한다. 조건 - 2 ≤ N ≤ 1,000,000 과정 이 문제에서 요구하는 것은 각 친구 즉, 노드들이 얼리 ..

백준 14267 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 풀이 전 나의 생각 상사가 직속 부하를 칭찬하며 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있을 때, 각자 얼마나 칭찬을 받았는지 구해야한다. 조건 - (2 ≤ n, m ≤ 100,000) - (2 ≤ i ≤ n, 1 ≤ w ≤ 1,000) - 1번의 경우, 상사가 없으므로 -1이 입력된다. - 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사..