허비의 기술블로그

가로, 세로의 크기가 각각 N, M인 직사각형에서 (3

그래프의 정점의 개수(N), 간선의 개수(M), 연결된 간선의 정보가 입력으로 주어진다. 이때 주어진 그래프에서 Connected Component(연결된 요소의 개수)를 구하는 문제다. 다음과 같은 그래프가 주어진다면 Connected Component의 개수는 3개이다. 시간 복잡도: O(MN) 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 풀이 과정 BFS나 DFS와 같은 그래프 탐색 방법을 활용하면 연결된 모든 노드(정점)를 방문할 수 있다..

입력으로 체스판의 크기 M * M, 나이트의 시작 위치, 이동하고자 하는 위치가 주어진다. 이때 나이트가 목적지까지 가는데 걸리는 최소 이동 횟수를 구하는 문제다. 시간 복잡도: O(M^2) 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 방법 나이트가 한번 이동할 때 갈 수 있는 위치는 다음과 같다. 총 8위치로 이동할 수 있으며 그때의 x, y좌표 변화는 위의 식과 같다. (체스판의 숫자는 dx, dy배열에서의 index) 체스판의 각 위치에 대응하는 M * M 크기의 2차원 배열을 선언하고, 값으로 ..