그래프 이론15 [백준/C,C++] 1389번: 케빈 베이컨의 6단계 법칙 www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이 각 유저를 출발 노드로 모든 노드를 방문할 때까지 BFS를 실행한 뒤, 모든 노드를 방문했을 때의 깊이(depth)를 더한 값이 가장 작은 노드를 출력하면 됩니다. 모든 정점에서 모든 정점을 방문해야 할 때, 플로이드 와샬이라는 알고리즘을 사용할 수 있던데 자세한 내용은 ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4.. 2021. 4. 21. [백준/C,C++] 10026번: 적록색약 www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 hackids.tistory.com/77 [백준/C,C++] 2667번: 단지번호붙이기 www.acmicpc.net/problem/2667 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙 hackids.tistory.com 2667번: 단지번호붙이기와 마찬가지로 한 정점에서.. 2021. 4. 21. [백준/C,C++] 7562번: 나이트의 이동 www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 최단 거리를 찾는 문제이기 때문에 전형적인 BFS 문제라고 볼 수 있습니다. 가장 기본적인 2차원 배열 위에서 상하좌우로 이동 가능한 미로 문제 등과 달리 나이트가 이동 가능한 8방향으로 이동하며 탐색합니다. 역시나 depth를 계산해 주면 되는 문제고 특별히 어려운 점은 없습니다. #include #include #include #define py first #define px second using na.. 2021. 4. 21. [백준/C,C++] 7576번: 토마토 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 2차원 배열이 주어지는 여타 다른 BFS 문제들과 비슷합니다. 크게 다른 점은 출발 지점이 정해져 있지 않다는 건데요. 익은 토마토, 즉 1인 지점을 모두 시작 지점으로 BFS를 실행시켜야 한다는 겁니다. 6 4 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 과 같은 예제가 입력되었다고 봅시다. 1일이 지난 후 토마토들은 아래와 같게 됩니다. 1 1 .. 2021. 4. 20. 이전 1 2 3 4 다음