[백준 BOJ / Python] 1976번 트리의 지름 (DFS)
문제트리는 사이클이 없는 무방향 그래프이며, 두 노드 사이의 경로가 항상 하나만 존재한다.두 노드를 선택하여 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우를 트리의 지름이라고 한다.입력으로는 루트가 있는 가중치가 있는 간선들로 이루어진 트리가 주어지며, 트리의 지름을 구하는 프로그램을 작성해야 합니다.풀이트리의 지름을 찾기 위해 DFS를 활용한다.트리의 임의의 노드
문제NxM 크기의 격자 미로 안에서 출발지 (x, y)에서 도착지 (r, c)로 가는 경로를 알파벳으로 표기했을 때, 사전 순으로 가장 빠른 경로를 찾는 문제이다.미로를 탈출하기 위해서 이동하는 거리는 k여야 한다. ( 이동거리 = 이동 횟수 = 경로 문자열 길이 )경로는 u(상), d(하), l(좌), r(우) 로 표현 가능하며 사전 순으로 가장 빠른 경로를 선택한다. 풀이깊이 우선 탐색(DFS) 알고리즘을 활용하여 경로를 찾을 수 있다.DFS 알고리즘은 LIFO(Last In First Out)의 특징을 갖고 있기 때문에 사전순으로 앞서는 알파벳을 뒤에서 탐색한다면 항상 사전순으로 빠른 문자열을 먼저 탐색할 수 있다.탐색 방향을 u, r, l, d 순으로 설정한다.한 노드에서 상하좌우로 이동할 때 u..
[백준 BOJ / Python] 2583번 영역 구하기
문제 모눈종이 위에 k개의 직사각형을 그릴 때, 직사각형이 그려지지 않은 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 m = 5, n = 7 인 모눈종이 위에 3개의 직사각형을 그렸을 때, 다음과 같이 3개의 영역으로 나누어질 수 있다. 각각의 넓이는 1, 7, 13이다. 이와 같이 직사각형에 포함되지 않는 분리된 영역의 각 크기를 오름차순으로 출력하는 문제이다. 풀이 먼저 주어진 직사각형을 모눈종이 영역에 표시한다. 이때 본 문제에서는 상하좌우 방향을 유의해야 한다. 여기서는 직사각형이 차지하는 공간이 중요한 부분임으로 임의로 row를 m, col를 n으로 보고, 왼쪽 아래 꼭짓점의 x1, y1좌표값과 오른쪽 위 꼭짓점의 x2, y2좌표값을 왼쪽 위, 오른쪽 아래로 가정하였다. (편의상 상하..
[알고리즘] 이분 그래프 (Bipartite Graph)
인접한 노드(정점)끼리 서로 다른 색으로 칠해서 두 가지 색으로 분할할 수 있는 그래프를 이분 그래프라고 한다. 즉 각각의 집합에 속한 노드끼리는 서로 인접하지 않도록 분할하는 것이다. 시간복잡도: O(V+E) 1. 이분 그래프 알고리즘 BFS, DFS 를 사용하여 이분 그래프인지 여부를 확인 가능하다. 판단 방법 서로 인접한 노드가 같은 색이면 이분 그래프가 아니다. BFS, DFS로 노드를 방문할 때마다 두 가지 중 한가지 색으로 칠한다. (1 혹은 2) 이때 인접한 노드와는 서로 다른 색을 선택한다. 즉, 현재 노드의 색(1)과는 다른 색(2)으로 연결된 다음 노드를 칠한다. 여기서 0은 방문하지 않음을 뜻하고 1 혹은 2는 서로 다른 색을 뜻한다. $color_{next}= color_{befor..