WannaBeDeveloper

2636번: 치즈 www.acmicpc.net 이 문제는 공기에 닿으면 녹는 치즈가 직사각형 모양의 판에 있을 때 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈 조각이 놓여 있는 칸의 개수를 구하는 문제이다. 단, 치즈 조각은 정사각형 모양의 칸 안에 들어있고 공기에 닿는 면이 하나라도 있으면 한 시간 후에 녹는다. 그리고 치즈로 둘러싸인 빈 공간은 공기가 없다고 가정한다. 이는 BFS 탐색을 이용해 쉽게 해결할 수 있다. 우선 판의 둘레 부분은 항상 공기로 이루어져 있으므로 판의 둘레 부분 중 아무데서나 BFS를 시작해 모든 공기층을 탐색한다. 그리고 치즈 조각 중 이 공기층과 맞닿아 있는 조각들을 없앤다. 이 과정을 모든 치즈가 사라질 때까지 반복하면 된다. 이를 코드로..

1103번: 게임 www.acmicpc.net 이 문제는 1부터 9까지의 숫자와 구멍이 있는 직사각형 보드에서 게임을 할 때 최대 몇 번의 동전을 움직일 수 있는지를 구하는 문제이다. 동전을 움직이는 규칙은 위와 같다. 이 문제를 해결하기 위해서는 왼쪽 위에서 시작하는 DFS를 수행해 동전의 이동 횟수의 최댓값을 구해야한다. DFS는 재귀 함수로 구현할 수 있다. 우선 함수 구현 전에 각 지점을 방문했음을 나타내는 N*M 크기의 visitied 행렬(초기값은 False)과 동서남북 방향을 나타내기 위한 dx, dy가 필요하다. 이제 DFS 함수를 구현해보자. 우선 DFS 함수는 인자로 방문하고자 하는 지점의 좌표 (x, y)를 받는다. 이 지점을 방문했다는 의미로 visited에서 해당하는 지점의 값을 ..

1068번: 트리 www.acmicpc.net 이 문제는 트리에서 노드 하나를 지웠을 때 남은 트리에서 리프 노드의 개수를 구하는 문제이다. 이 문제는 트리를 각 노드의 부모 노드를 표현하는 배열로 나타내기 때문에 노드 하나를 단순히 제거하기는 쉽지 않다. 노드 하나를 제거할 때 그 노드의 자식 노드 역시 제거되기 때문에, 이를 부모 노드를 표현하는 배열에 반영해야 한다. 노드 하나를 제거하는 함수를 구현해보자. 우선 각 노드의 부모 노드를 표현하는 배열을 parents라 하고, 노드 u를 제거하는 경우 이를 parents 배열에는 parents[u] = -2로 반영한다고 하자. 그러면 노드 v를 제거하는 함수에서는 우선 parents[v]를 -2로 하고, 모든 노드를 순회하면서 만약 부모 노드가 v인 ..

13549번: 숨바꼭질 3 www.acmicpc.net 이 문제는 이전의 숨바꼭질 문제에서 순간이동에 걸리는 시간이 1초가 아닌 0초인 경우 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지를 구하는 문제이다. 백준 1697번 : 숨바꼭질 in Python 1697번: 숨바꼭질 www.acmicpc.net 위 문제는 어떤 한 점에서 다른 한 점으로 가기 위해 걸리는 최단 시간을 구하는 문제로, 이동 방법에는 앞뒤로 한 칸 또는 그 점의 좌표만큼 앞으로 이동하는 방법이 있다. 만.. wanna-be-developer-yjh.tistory.com 이 문제는 기존의 숨바꼭질 문제와는 달리 순간이동에 걸리는 시간이 0초이기 때문에 BFS로 알고리즘을 구현할 때 순간이동을 별도로 구현할 필요가 있다...

1328번: 고층 빌딩 www.acmicpc.net 이 문제는 높이가 모두 다른 빌딩 N개가 한 줄로 세워져 있고, 이를 왼쪽 끝과 오른쪽 끝에 서서 봤을 때 보이는 빌딩 수를 알 때 가능한 빌딩 순서의 경우의 수를 구하는 문제이다. 이 문제는 단순히 순열과 조합만을 이용해 경우의 수를 구하기는 어렵다. 빌딩의 높이에 따라 가려지는 빌딩이 달라지고, 또한 가려지는 빌딩의 수 역시 고려해야 하기 때문이다. 그래서 다른 방법을 이용해 문제를 해결해야 한다. 어떤 방법으로 해결할 수 있을까? N-1개의 빌딩이 한 줄로 세워져 있을 때 모든 L, R(1

2146번: 다리 만들기 www.acmicpc.net 이 문제는 여러 섬으로 이루어진 나라에서 한 섬과 다른 섬을 잇는 다리 중 가장 짧은 것의 길이를 구하는 문제이다. 이 문제를 해결하기 위해서는 각 섬의 위치를 파악하고, 임의의 서로 다른 두 섬 사이의 최단 거리를 구해야 한다. 먼저 각 섬의 위치를 파악하기 위해서는, 지도 내 모든 좌표를 순회하면서 해당 좌표가 육지인 경우 그 지점을 시작으로 그래프 탐색을 시행해야 한다. 단, 이때는 섬의 위치를 파악하기 위해 그래프를 탐색하고 있으므로 이웃한 지점 중 육지인 지점만 탐색한다. 그리고 각 지점이 어떤 섬에 속하는지를 저장해야 한다. 이를 위해 각 섬에 부여할 숫자를 저장하는 변수 cnt를 만들고, 지도 내 좌표를 순회하는 중 방문하지 않은 지점을 ..

2589번: 보물섬 www.acmicpc.net 이 문제는 보물 지도가 주어질 때 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 문제이다. 단, 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 우선, 보물의 위치를 알기 위해서, 그리고 보물 간의 최단 거리를 구하기 위해서는 결국 지도 내 두 지점 사이의 최단 거리를 구해야 한다. 그러므로 이 문제는 그래프 탐색 중 너비 우선 탐색을 이용해야 한다. 만약 보물의 위치만 알 수 있다면 이를 너비 우선 탐색을 이용해 최단 거리를 쉽게 구할 수 있을 것이다. 그렇다면 보물의 위치는 어떻게 구할 수 있을까? 보물은 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻..

2688번: 줄어들지 않아 www.acmicpc.net 이 문제는 줄어들지 않는 n자리 수의 개수를 구하는 문제이다. 여기서 줄어들지 않는 수란 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같은 수를 말한다. 이는 dynamic programming으로 쉽게 해결할 수 있다. (i+1)자리 수의 맨 앞자리 수가 j일 때 줄어들지 않는 수의 개수를 (i, j) 성분에 저장하는 (n+1)*10 크기의 행렬 dp를 만들고, 초기값으로 dp[0][i] ( i = 0, ... , 9)를 1로 한다. 그 다음 i가 1일 때부터 n일 때까지 순회하면서 (i+1)자리 수의 줄어들지 않는 수의 개수를 구한다. 줄어들지 않는 수의 개수를 구할 때 맨 앞자리의 수가 j로 정해지면 그 뒤자리에 나올 수 있는 수는 j..

11062번: 카드 게임 www.acmicpc.net 이 문제는 근우와 명우가 매번 돌아가면서 일렬로 놓은 N개의 카드 중 왼쪽 끝 또는 오른쪽 끝에 있는 카드를 가져갈 때 근우가 얻는 점수를 구하는 문제이다. 단, 점수는 카드에 적힌 숫자의 합과 같고, 두 사람은 최선의 전략으로 게임에 임한다. 여기서 최선의 전략은 단순히 매번 더 높은 점수가 적힌 카드를 뽑는 전략이 아닌, 전체적으로 가장 높은 점수를 얻기 위해 상대의 선택 역시 고려하면서 카드를 뽑아야 함을 의미한다. 예를 들어 1, 2, 5, 2가 적힌 4장의 카드를 번갈아가면서 뽑을 때, 단순히 오른쪽 끝 카드에 적힌 숫자가 더 크다고 해서 오른쪽 끝 카드를 뽑으면 상대방은 1이 적힌 카드와 5가 적힌 카드 중 5가 적힌 카드를 뽑을 것이고, ..

9466번: 텀 프로젝트 www.acmicpc.net 이 문제는 텀 프로젝트를 수행하기 위해 학생들 간에 프로젝트 팀을 구성할 때, 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 구하는 문제이다. 단, 모든 학생은 프로젝트를 함께하고 싶은 학생을 한 명만 선택할 수 있고, 프로젝트 팀을 구성하기 위해서는 학생을 s_1, s_2, ... ,s_r이라 할 때 s_1은 s_2를, s_2는 s_3를, ..., 그리고 s_r은 s_1을 선택해야 (s_1, s_2, ... ,s_r)이 한 팀을 이룰 수 있다. r=1인 경우, 즉 s_1이 자기 자신을 택하는 경우도 포함한다. 이 문제는 설명이 복잡하지만 결국 구하고자 하는 것은 학생들을 그래프의 정점, 프로젝트를 함께하고 싶은 학생을 선택하는 것을 그래프의 간선이..