Kwin's Development Diary.

문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. ..

문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 문제 접근 방법 이번 문제는 입력으로 주어진 그래프의 연결 요소의 개수를 파악하는 문제이다. 이때, 연결 요소란? 한 정점에서 출발하여 도착할 수 있는 정점들의 집합이라 생각하면 쉽다. 이게 무슨 의미냐면 정점 V1과 간선을 통해 해당 정점 Vn에 도착할 수 있다면 같은 연결 ..

깊이 우선 탐색(Depth First Search, DFS) : 하나의 정점으로부터 시작하여 깊은 곳 우선으로 탐색하여 최종적으로 연결된 모든 정점을 탐색하는 방법 특징 ① 경로상의 노드들만 기억하면 되므로 차지하는 저장 공간이 적다. ② 같은 레벨의 경로보다 더 깊은 레벨을 우선으로 탐색한다. ③ 재귀적으로 동작하며, 후입 선출(LIFO, Last In First Out) 구조이다. 알고리즘 ① 시작 정점 v를 결정하여 방문 ② 정점 v에 인접한 정점 중 1. 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push 하고 w를 방문하고 w를 v에 대입하여 ②과정 반복 수행 2. 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해 마지막 방문 정점을 스택을 pop 하여 받은 정점 v로 하여 다시..

문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추 흰 지렁이를 구입하기로 결심한다. 이 지렁이는 배추 근처에 서식하며 해충을 잡아먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추 흰 지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추 흰 지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추..

문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수..

문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선 상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그다음 N 줄에는 각각 N개의 자료(0 혹은 1)가 입력된다. 출력 첫 번째 줄에는 총 단지수를 출력하시오. 그리고 ..

신장 트리(Spanning Tree : ST) - n개의 정점으로 이루어진 무방향 그래프에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리 깊이 우선 신장 트리(Depth First Spanning Tree) / 너비 우선 신장 트리(Breadth First Spanning Tree) 최소 비용 신장 트리(Minimum Cost Spanning Tree : MST) - 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 - 최소 비용 신장 트리를 만드는 알고리즘 ㄴ Kruskal 알고리즘 [알고리즘] 크루스칼 알고리즘(Kruskal Algorithm) - JAVA / 자바 ㄴ Prime 알고리즘 [알고리즘] 프림 알고리즘(Prim Algorithm) - JAVA ..

그래프 순회(graph traversal), 그래프 탐색(graph search) - 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 처리하는 연산 - 그래프 탐색 방법 ㄴ 깊이 우선 탐색 (Depth First Search : DFS) ㄴ 너비 우선 탐색 (Breadth First Search : BFS) 깊이 우선 탐색(Depth First Search : DFS) >>> A - B - D - G - E - C - F ① 시작 정점 v를 결정하여 방문 ② 정점 v에 인접한 정점 중 1. 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push 하고 w를 방문하고 w를 v에 대입하여 ②과정 반복 수행 2. 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해 마지막 방문 정..