문제1부터 N까지의 정수로 이루어진 순열을 오름차순으로 정렬할 때, 최소 몇 번의 뒤집기를 해야 하는지 구하는 문제이다.정렬은 특정 위치 iii에서 시작하여 오른쪽으로 K개의 숫자를 뒤집는 연산을 반복하는 방식으로 이루어진다. 예를 들어 N이 5, K가 3일 때, (5, 4, 3, 2, 1) 순열이 주어진 경우i=0에서 뒤집으면 (3, 4, 5, 2, 1) 이 된다.i=1에서 뒤집으면 (3, 2, 5, 4, 1) 이 된다.i=2에서 뒤집으면 (3, 2, 1, 4, 5) 이 된다.i=0에서 뒤집으면 (1, 2, 3, 4, 5) 이 되면서 정렬이 완료된다.최소 4번의 뒤집기로 오름차순 순열을 만들 수 있다.풀이이 문제는 각 순열 상태를 노드로 보고, 한 번의 뒤집기로 다른 상태로 이동하는 최단 경로 탐색 문..
문제주어진 문제는 N×M 크기의 격자에서 빙하(1)와 물(0)의 상태를 표현하는 배열을 통해, 빙하가 전부 녹는 데 걸리는 시간과 마지막으로 녹은 빙하의 크기를 계산하는 것이다. 빙하는 매 초마다 상하좌우로 인접한 물과 접촉하여 동시에 녹는데, 빙하로 둘러싸여 있는 물의 경우에는 붙어 있는 빙하를 녹이지 못한다. 최종적으로 빙하가 모두 녹을 때까지의 시간과 마지막으로 녹은 빙하의 크기를 출력해야 한다. 풀이바깥쪽에 있는 물이 빙하와 접촉하면 해당 빙하가 녹지만, 안쪽에 있는 물은 빙하에 영향을 미치지 않는다는 점이 중요하다.이를 해결하기 위해 BFS 알고리즘을 사용하여 바깥쪽 물을 중심으로 탐색하면서 빙하를 만나면 녹이도록 한다.이 과정에서 빙하가 녹은 자리는 물의 영역으로 간주될 수 있기 때문에, 기존..
[백준 BOJ / Python] 1707번 이분 그래프 (Bipartite Graph)
문제 그래프의 정점을 두 집합으로 분할할 때, 인접한 정점끼리 서로 다른 집합에 포함되는 그래프를 이분 그래프라고 한다. 주어진 그래프가 이분 그래프인지 판별하는 문제이다. 풀이 이분 그래프인지 확인하기 위해서 정점들을 두 가지 색으로 칠할 때, 인접한 정점끼리 서로 다른 색으로 칠할 수 있는지를 확인하면 된다. 즉, 인접한 정점이 같은 색이라면 이분 그래프가 아닌 것이다. 예를 들어 a를 노란색(1)으로 칠한다면, a와 연결된 b,c,d를 초록색(2)으로 칠하는 것이다. 그 다음 b,c,d에 연결된 인접한 정점들을 다시 노란색(1)로 칠하다가 이미 다른 색으로 칠해진 정점을 만났을 때, b,c,d와 같은 초록색(2)이 칠해져 있다면 이분 그래프가 아니라고 판별할 수 있다. 반대로 모든 정점들을 방문해도..
[알고리즘] 이분 그래프 (Bipartite Graph)
인접한 노드(정점)끼리 서로 다른 색으로 칠해서 두 가지 색으로 분할할 수 있는 그래프를 이분 그래프라고 한다. 즉 각각의 집합에 속한 노드끼리는 서로 인접하지 않도록 분할하는 것이다. 시간복잡도: O(V+E) 1. 이분 그래프 알고리즘 BFS, DFS 를 사용하여 이분 그래프인지 여부를 확인 가능하다. 판단 방법 서로 인접한 노드가 같은 색이면 이분 그래프가 아니다. BFS, DFS로 노드를 방문할 때마다 두 가지 중 한가지 색으로 칠한다. (1 혹은 2) 이때 인접한 노드와는 서로 다른 색을 선택한다. 즉, 현재 노드의 색(1)과는 다른 색(2)으로 연결된 다음 노드를 칠한다. 여기서 0은 방문하지 않음을 뜻하고 1 혹은 2는 서로 다른 색을 뜻한다. $color_{next}= color_{befor..