WannaBeDeveloper

16236번: 아기 상어 www.acmicpc.net 이 문제는 여러 마리의 물고기와 한 마리의 아기 상어가 있는 공간에서 아기 상어가 자신이 먹을 수 있는 물고기를 다 먹을 때까지 걸리는 시간을 구하는 문제이다. 이때 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 못 지나가고, 자신의 크기보다 작은 물고기는 먹을 수 있다. 그리고 먹을 수 있는 물고기들 중 항상 거리가 가까운 물고기를 먹으러 간다. 이때 거리가 가까운 물고기가 많은 경우 가장 위에 있는 물고기, 가장 왼쪽에 있는 물고기 순으로 먹는다. 우선 매번 물고기를 먹은 뒤에 아기 상어의 위치를 기준으로 가장 가까운 물고기를 찾아야 하므로 이를 구현하는 함수를 만들어야 한다. 이때 이를 찾기 위해서는 BFS를 실행해야 하므로, 따라서 상어의..

1922번: 네트워크 연결 www.acmicpc.net 이 문제는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축할 때 드는 비용의 최솟값을 구하는 문제이다. 이는 각 컴퓨터를 노드로, 컴퓨터 사이를 연결하는 선은 간선으로 볼 때 그 결과 나오는 그래프의 minimum spanning tree를 구하는 문제로 볼 수 있다. 따라서 MST를 구하기 위한 Kruskal's algorithm이나 Prim's algorithm을 이용하면 되는데, 여기서는 Kruskal's algorithm을 사용한다. 즉, 모든 노드마다 하나의 집합으로 간주한 뒤, 주어진 간선들을 비용이 적은 순서대로 저장한다. 그리고 간선을 하나씩 꺼내면서 간선의 양 끝 점이 같은 집합 안에 있지 않은 경우 연결하는 것을 반복한다. 이때 같..

2644번: 촌수계산 www.acmicpc.net 이 문제는 여러 사람들에 대한 부모 자식 관계가 주어졌을 때 주어진 두 사람의 촌수를 계산하는 문제이다. 단, 각 사람의 부모는 최대 한 명만 주어진다. 이를 해결하기 위해서는 문제에서도 직관적으로 알 수 있듯이 각 사람들을 하나의 노드로 하고 부모 자식 관계는 간선으로 표현한 트리를 만들면 된다. 특히 문제의 조건 중에 각 사람의 부모가 최대 한 명이라는 조건에 의해 각 노드마다 부모 노드는 두 개 이상 될 수 없어 이를 구현하는데 문제가 없다. 트리는 각 노드마다 부모 노드의 번호를 저장하는 배열 parent를 만들어 구현한다. 예를 들어 n 9일 때 부모 자식 관계가 주어질 때 1 2라는 input이 주어지면 2의 부모가 1이라는 의미이므로 pare..

13460번: 구슬 탈출 2 www.acmicpc.net 이 문제는 직사각형 보드에서 구멍을 통해 빨간 구슬을 빼낼 때 보드를 기울이는 횟수의 최솟값을 구하는 문제이다. 단, 파란 구슬이 구멍으로 빠지면 안 된다. 우선 이 문제는 그래프 탐색 문제로 볼 수 있고, 특히 구슬들의 이동 횟수의 최솟값을 묻고 있기 때문에 너비 우선 탐색을 적용해야 한다. 단, 이동할 때 한 칸씩 움직이는 게 아니라 벽이나 구멍, 다른 구슬을 만날 때까지 움직이기 때문에 이를 구현할 때 주의해야 한다. 보드를 한쪽 방향으로 기울였을 때 구슬이 움직이는 것을 구현하는 함수를 만들어보자. 우선 매개변수로 그 구슬의 현재 좌표와 이동 방향이 주어져야 할 것이다. 그리고 구슬은 벽이나 구멍을 만날 때까지 움직이므로 while의 조건문..

10026번: 적록색약 www.acmicpc.net 이 문제는 빨강, 초록, 파랑으로 색칠한 그림이 주어졌을 때 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 문제이다. 구역이란 어떤 사람이 봤을 때 모두 같은 색으로 이루어진 영역을 말한다. 즉, 적록색약이 아닌 경우에는 빨강, 초록, 파랑을 구별해 같은 색으로 이루어진 구역의 수를 구하는 반면, 적록색약인 경우에는 빨강과 초록을 하나의 색으로 취급해 같은 색으로 이루어진 구역의 수를 구하면 된다. 여러 해결 방법이 있지만, 여기서는 적록색약이 아닌 경우와 적록색약인 경우 각각에 대해 바라본 그림에 대응하는 행렬을 만들어 각 행렬에 그래프 탐색을 이용해 구역의 개수를 구하는 방식으로 문제를 해결한다. 우선 위에서 말한 행렬 두 개..

2583번: 영역 구하기 www.acmicpc.net 이 문제는 M*N 크기의 모눈종이가 있고 여기에 K개의 직사각형을 그릴 때 K개의 직사각형의 내부를 제외한 나머지 부분이 여러 개의 영역으로 나누어지는데, 이때 영역의 개수와 각 영역의 넓이를 구하는 문제이다. 이를 해결하기 위해서는 우선 모눈종이의 각 칸이 하나의 entry에 대응하는 M*N 행렬 paper를 만들고, 직사각형의 내부의 칸에 대응하는 entry의 값을 1로, 나머지 entry는 0으로 한다. 이때 문제에서 나오는 input은 직사각형의 왼쪽 아래의 좌표와 오른쪽 위 좌표가 주어지는데, 실제로 paper의 각 entry는 하나의 칸에 대응하고, entry의 행과 열은 각각 모눈종이 내 해당 칸의 왼쪽 아래 점의 y좌표, x좌표와 같다...

1987번: 알파벳 www.acmicpc.net 이 문제는 각 칸에 대문자 알파벳이 하나씩 적혀 있는 R*C 크기의 보드가 있을 때 좌측 상단 칸에서 출발한 말이 지금까지 지나온 칸에 적힌 알파벳과 같은 알파벳이 적힌 칸을 지날 수 없을 때 최대 몇 칸을 지날 수 있는지를 구하는 문제이다. 이를 해결하기 위해서는 좌측 상단 칸에서 DFS를 시행하되, 현재까지 지나온 칸에 적힌 알파벳들을 따로 저장해둬 다음에 지날 칸에 적힌 알파벳이 이 알파벳 중 하나가 되지 않는 경우에만 해당 칸으로 진행하도록 함수를 작성한다. 그리고 백트래킹을 사용해 결과값을 반환하기 전에 현재 지난 칸에 해당하는 알파벳을 지워 후에 다른 경로를 통해 DFS를 시행할 때 정상적으로 해당 칸에 대한 방문을 할 수 있도록 한다. 이를 코..

2468번: 안전 영역 www.acmicpc.net 이 문제는 어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 문제이다. 여기서 안전한 영역이란 강수량보다 해당 지역의 높이가 더 높아 물에 잠기지 않는 지점들의 집합 중 지점들끼리 서로 인접한 최대 영역을 말한다. 우선 특정 강수량이 주어진 경우를 생각해보자. 그러면 그 강수량에 대한 안전한 영역의 개수를 구하는 문제는 이전의 섬의 개수 문제와 거의 동일하다. 단지 안전한 영역을 찾기 위해 강수량보다 지점의 높이가 더 높은 지점에 대해서만 그래프 탐색을 한다는 점만 다를 뿐이다. 백준 4963번 : 섬의 개수 in Python 4963번: 섬의 개수 www.acmicpc.net 이 문제는 섬과 바다 지..

11403번: 경로 찾기 www.acmicpc.net 이 문제는 방향 그래프가 인접행렬 형식으로 주어졌을 때 모든 정점 쌍 (i, j)에 대해 i에서 j로 가는 경로가 있는지 없는지를 구하는 문제이다. 만약 주어진 그래프가 방향이 없는 간선만 주어졌다면 disjoint set operation을 이용해 임의의 두 정점 쌍이 연결되어 있는지를 쉽게 확인할 수 있다. 하지만 이 문제는 방향이 있는 간선이 주어지는 경우이므로 그래프 탐색을 통해 임의의 점과 연결된 모든 점을 찾는 방식으로 문제를 해결해야 한다. 여기서 주의해야 할 점은 임의의 점과 연결된 점을 찾을 때 자기 자신을 포함하는 경우는 자신을 포함하는 사이클이 있는 경우뿐이라는 점이다. 이를 코드로 구현하면 다음과 같다. from collectio..

4963번: 섬의 개수 www.acmicpc.net 이 문제는 섬과 바다 지도가 주어질 때 섬의 개수를 세는 문제이다. 단, 두 정사각형이 같은 섬에 있기 위해서는 두 정사각형이 가로, 세로 또는 대각선으로 인접하고 있어야 한다. 이는 그래프 탐색을 이용해 쉽게 해결할 수 있다. 우선 깊이 우선 탐색이나 너비 우선 탐색 중 하나를 구현한 뒤, 지도 내 모든 정사각형을 방문하면서 만약 해당 정사각형이 섬의 일부인 경우 그 정사각형과 연결되어 있고, 섬의 일부인 모든 정사각형을 방문하는 그래프 탐색을 진행한다. 그러면 이후 그 섬을 다시 방문했을 경우 이미 방문한 섬이기에 섬의 개수를 셀 때 영향을 끼치지 않는다. 단, 보통 문제와는 달리 두 정사각형이 가로, 세로, 또는 대각선으로 인접한 경우 하나의 섬 ..