허비의 기술블로그

R X C의 2차원 보드의 각 위치에 영문 대문자가 들어있다. (0, 0)의 좌표에서 상하좌우 중 한 방향으로 이동하려고 하는데, 가려고 하는 좌표의 값이 이미 지나온 경로에 있는 값이라면 갈 수 없다. 이때 이동할 수 있는 최대 거리를 구하는 문제이다. 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 과정 (0, 0)의 좌표에서 이동하면서 현재까지 지나온 값을 저장해야 한다. 보드의 값이 대문자 알파벳(A ~ Z) 26개로 한정돼 있으므로 26개 길이의 배열을 선언해 각 알파벳의 사용 여부 (T..

가로, 세로의 크기가 각각 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와 같은 그래프 탐색 방법을 활용하면 연결된 모든 노드(정점)를 방문할 수 있다..