WannaBeDeveloper

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

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

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

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

5014번: 스타트링크 www.acmicpc.net 이 문제는 F층으로 이루어진 고층 건물에서 위로 U층을 가는 버튼과 아래로 D층을 가는 버튼만을 가지는 엘리베이터를 타고 S층에서 G층으로 가려고 할 때 눌러야 하는 버튼의 최소 횟수를 구하는 문제이다. 이때 U와 D의 값에 따라 도달할 수 없는 층이 존재할 수 있는데, 그때는 'use the stairs'를 출력한다. 이를 해결하기 위해서는 S층을 시작으로 하는 BFS를 시행해야 한다. 즉, S층을 시작으로(즉, S를 queue에 넣은 뒤 while loop에서 S를 꺼낸다.) 위로 U층 가는 경우와 아래로 D층 가는 경우를 고려해 만약 도착한 곳이 1층 이상 F층 이하이고, 아직 방문하지 않은 곳이라면 해당 층을 방문했다고 표시하고, 그 층을 방문할..

2573번: 빙산 www.acmicpc.net 이 문제는 한 덩어리의 빙산이 주어질 때 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 문제이다. 1년의 시간이 지났을 때 빙산 내 각 칸의 높이는 그 칸이 동서남북으로 이웃한 칸 중 빙산이 없는 칸의 수만큼 감소한다. 이 문제는 복잡해 보이지만 결국 구현해야 하는 것은 크게 현재 시점에서 빙산의 개수를 세는 함수와, 1년의 시간이 지났을 때 빙산의 변화를 구현하는 함수로 나눌 수 있다. 우선 현재 시점에서 빙산의 개수를 세는 것은 주어진 행렬을 바탕으로 그래프 탐색을 수행하면 쉽게 얻을 수 있다. 즉, 행렬 내 모든 entry를 순회하면서 값이 양수인 지점을 찾아 그 지점을 시작으로 너비 우선 탐색(또는 깊이 우선 탐색)을 시행해 그 지..

1261번: 알고스팟 www.acmicpc.net 이 문제는 미로가 주어질 때 맨 왼쪽 위 지점(좌표로 치면 (1, 1) 지점)에서 출발해 맨 오른쪽 아래 지점(좌표로 치면 (N, M) 지점)으로 이동하기 위해서 최소 몇 개의 벽을 부수어야 하는지를 구하는 문제이다. 우선 벽을 부술 수 없는 경우에는 (1, 1) 지점에서 (N, M) 지점으로 가는 최단 경로를 찾기 위해 BFS, 즉 너비 우선 탐색을 이용했다. 그러므로 벽을 최대한 덜 부수기 위해서, 즉 최대한 벽이 없는 경로를 따라가기 위해서 BFS를 이용한다. 여기에 더해, 벽을 부수는 경우 역시 고려해야 하는데, 여기서는 dynamic programming을 활용한다. 미로 내 각 좌표마다 그 좌표까지 도달하기 위해 부숴야 하는 벽의 갯수의 최솟값..

16234번: 인구 이동 www.acmicpc.net 이 문제는 각 나라의 인구수가 주어졌을 때 인구 이동이 몇 번 발생하는지 구하는 문제이다. 인구 이동의 조건은 위와 같다. 이 문제를 해결하기 위해서는 대략적으로 다음과 같은 과정을 거쳐야 한다. 우선 각 나라에 대해 그 나라를 포함하는 나라들의 연합을 만들고, 연합 내 모든 국가들의 인구 수를 모든 국가들의 인구 수의 평균으로 바꿔야 한다. 이를 방문하지 않은 모든 나라에 대해 수행하고 만약 인구 이동이 발생하지 않은 경우 위 과정을 끝내고, 인구 이동이 발생한 경우 다시 위 과정을 반복한다. 좀 더 구체적으로 위 과정을 구현하자. 우선 특정 나라의 위치가 주어질 때 그 나라를 포함하는 연합을 구하고 연합 내 나라들의 인구 수를 바꾸는 함수 BFS를..

1389번: 케빈 베이컨의 6단계 법칙 www.acmicpc.net 이 문제는 친구 관계가 주어졌을 때 케빈 베이컨의 수가 가장 적은 사람을 구하는 문제이다. 이떄 어떤 사람의 케빈 베이컨의 수란 각 사람마다 몇 명의 친구를 거쳐야 도달할 수 있는지를 구한 뒤 이를 모두 더한 결과이다. 겉으로 보기에는 복잡해 보이지만, 사실 각 사람마다 BFS를 이용해 다른 사람과의 거리를 구하고, 이를 모두 더하면 케빈 베이컨 수를 구할 수 있다. 그러므로 BFS를 모든 사람에 대해 적용한 뒤 케빈 베이컨 수를 구하고 케빈 베이컨 수가 최소가 되는 사람을 구하면 된다. 이를 코드로 구현하면 다음과 같다. import sys from collections import deque N, M = map(int, input()..

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