공부하자

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 이 문제 또한 백준 #2667 단지 번호 붙이기와 유사한 문제이다. 주어진 행렬 형태의 그래프를 순회하며 같은 문자로 묶인 구역을 탐색하는 문제인데, 이 문제와 다른 문제들의 차별점이라 함은 행렬에서 나타나는 알파벳이 여러가지이고, 그 알파벳들을 각기 다른 구역으로 판별하여 탐색하여야한다. 따라서 기존에 사용하던 BFS 함수 포맷에 char 인자를 하나 더 전달하여 각기 다른 알파벳들을 따..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 가중치가 없는 그래프에서의 최단경로 찾기. 역시나 BFS를 활용하는 문제이다. 인접리스트 형식이 아닌 숫자 행렬로 입력이 주어지기 때문에 상하좌우 연산을 통해서 그래프를 탐색하고, 목적지까지의 거리를 계산하기 위해 중간중간에 거치는 정점마다의 거리값 배열인 dist를 이용하여 해결했다. 다만 도중에 scanf에서 &arr[i][j]와 같이 이중반복문으로 배열의 인덱스에 직접 접근하여 입력했는데, 숫자가 공백없이 주어지다 보니 입..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 그간 일본여행을 다녀오느라 블로그나 공부를 제대로 못했었는데 역시 오랜만에 하니까 기억이 잘 안난다. PS는 그 무엇보다 그냥 매일 꾸준히 하는것이 실력향상을 위한 가장 빠른길인듯 하다. 이 문제는 #2667 단지번호붙이기와 비슷한 유형의 문제다. 이전에 블로그에 올렸던 문제이기도 한데, 1. 가중치가 없는 그래프에서 최단 경로를 찾아야 한다거나 2. 그런 최단 경로의 갯수를 구한다거나 3. 어떤 행렬이나 지..

다익스트라 알고리즘이란? 음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘이다. 한 정점에서 다른 정점까지의 최단 경로를 구하는데, 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. 그래프 탐색 알고리즘 중 최소 비용을 구하는 알고리즘은 다익스트라 외에도 벨만-포드 알고리즘 Bellman-Ford Algorithm, 플로이드-워셜 Floyd-Warshall 알고리즘 등이 있다. (벨만-포드 알고리즘은 음수 가중치의 그래프도 탐색 가능하다.) 그중에서도 다익스트라 알고리즘은 프림 알고리즘을 살짝 변형한 형태인데, 두 가지 차이점이 존재한다. 차이점은 다음과 같다. ..

https://www.acmicpc.net/problem/11724 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를 순회하면서 연결 요소의 갯수가 있는지 찾는 문제다. 처음엔 문제를 잘못 읽고 연결된 그래프가 몇개인지만 세아려서 출력하면 되는줄 알았는데, 아무 간선도 가지지않는 정점도 연결 요소에 포함시켜 구현해야 했다. 방향성 없고 가중치 없는 그래프다 보니 그냥 바로 BFS로 감을 잡고 풀었고, 백준 2606번 바이러스 문제와 유사한 ..

프림 알고리즘이란? 최소 신장 트리 (Minimum Spanning Tree, MST) 구현에 사용되는 알고리즘으로 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장하는 기법이다. 프림 알고리즘의 시퀀스 1. 시작할 정점을 MST집합에 넣는다. 2. MST집합에 속한 정점들과 인접한 정점들 중 가장 낮은 가중치의 간선과 연결된 정점을 MST집합에 넣는다. 3. 2번과정을 MST집합의 원소 개수가 그래프 정점의 갯수가 될 때까지 반복한다. 4. 만들어진 MST집합의 가중치를 다 더해서 MST Cost 산출. 크루스칼 알고리즘 vs 프림 알고리즘 크루스칼 알고리즘 : Kruskal's Algorithm 프림 알고리즘 : Prim's Algorithm 그래프의 최소 가중치 간선들을 정렬된 순서로 추가하여..

크루스칼 알고리즘이란? 최소 신장 트리 구현에 사용되는 알고리즘으로, 가중치가 있는 그래프의 모든 간선들을 대상으로 1. 최소 비용의 간선으로 구성 2. 사이클을 형성하지 않음 의 조건을 지켜가며 각 단계마다 최선의 해를 선택하기에 그리디 알고리즘에 기원을 둔다. 크루스칼 알고리즘의 시퀀스 1. 그래프의 간선들을 가중치 기준으로 오름차순 정렬한다. 2. 정렬된 간선들 중 가중치가 작은 순서대로 사이클을 형성하지 않는 한 선택한다. 3. 선택된 간선으로 MST를 구현한다. 4. MST 집합의 원소의 개수가 V-1개가 될때까지 위 단계를 반복한다. 이때, 주의해야 할 점은 사이클을 형성하지 않게 정렬된 간선들을 선택한다는 것이다. 따라서 사이클을 형성하는지 안하는지에 대한 판가름을 해줄 수 있는 메소드를 같..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net BFS 문제를 계속 풀어보고 있는데, 이 문제 또한 비슷한 형태의 알고리즘이다. BFS로 풀리는 문제는 정해진 몇몇개의 특징이 있는 듯 하다. 1. 가중치가 없는 그래프에서 최단 경로를 찾아야 한다거나 2. 그런 최단 경로의 갯수를 구한다거나 3. 어떤 행렬이나 지도를 주고 그 지도에서 같은 부분으로 묶이는 영역을 구한다거나 이런 특정한 조건이 들어간 문제가 있으면 웬만하면 BFS로 접근해라 라는 ..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net "가장 빠른 시간"을 구해야 하는 문제니 BFS를 적용하여 풀었다. 처음엔 그냥 산술적으로 브루트포스 같은것들을 적용시켜 도전하려 했으나, 주어지는 입력의 최댓값이 100,000이고, 제한시간이 2초니까 O(N^2)짜리 코드로 풀면 시간초과가 날것이다. 따라서, BFS를 이용하여 푸는쪽으로 방향을 잡았다. 그래프를 형태가 인접리스트로 주어지는것이 아니기 때문에 오로지 큐..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net BFS를 활용하면 금방 풀리는 문제이다. 입력으로 주어지는 그래프를 인접 리스트 형식으로 구현해놓고, BFS만 돌리면 끝이다. 다만 여기서 포인트는 BFS를 순회하면서 정점들을 기록하는것이 아닌 정점들의 갯수만 카운트 시키고, 마지막 출력할때에 카운트된 변수에서 1만 빼주면 된다. 문제에서 요구하는 출력 조건이 "1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수"이기 때문에 1번 컴퓨터 본인은..