난이도 : 골드 5 걸린 시간 : 1시간 30분 문제 DSLR 문제 바로가기 풀이 DSLR이라는 4가지 경로가 있다고 생각하고 bfs 코드 #include #include #include using namespace std; struct point { int prev; char state; int visited = -1; }; char dslrArr[4] = { 'D', 'S', 'L', 'R' }; int dslrResult(int type, int num) { int tmp; switch (type) { case 0 : return (num* 2) % 10000; case 1 : if (num == 0) return 9999; else return num - 1; case 2 : tmp = num /..

난이도 : 골드 3 걸린 시간 : 30분 문제 다리 만들기 문제 바로가기 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 가장 짧은 다리의 길이 == 가장 가까운 두 점 사이의 최단 거리 모든 섬 사이의 최단 거리를 구해야 함 각 섬에 속한 점들로부터 다른 섬의 점들까지의 최단 거리 계산 가중치 없으므로 bfs 이용 각 섬에 속하는 점들은 bfs로 따로 찾기 코드 #include #include using namespace std; int map[101][101]; int direction[4][2] = { ..

난이도 : 골드 5 걸린 시간 : 30분 문제 보물섬 문제 바로가기 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다. 예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다. 보물..

난이도 : 골드 4 걸린 시간 : 오래 걸림 문제 벽 부수고 이동하기 문제 보러가기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 풀이 모든 경로를 살펴볼 필요없..

난이도 : 골드 4 걸린 시간 : ㅎㅎ.. 오래 걸림 문제 아기 상어 문제 바로가기 풀이 bfs를 이용하여 먹을 수 있는 고기 찾기 + 상어로부터의 거리 찾기 거리가 가장 가까운 먹을 수 있는 고기들 찾기 그 중 가장 왼쪽 위에 있는 고기 찾기 상어가 해당 물고기의 위치로 이동해서 먹고, 먹은 물고기 개수가 size와 같아지면 size 키우기 상어보다 작은 물고기가 없을 때까지 반복 코드 #include #include #include using namespace std; struct shark { int r; int c; int size = 2; }; struct fish { int r; int c; int distance = 0; fish(int rp, int cp, int dist) { r = rp..

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

난이도 : 골드 5 걸린 시간 : 1시간 문제 연구소 문제 바로가기 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연..

난이도 : 골드 3 걸린 시간 : 45분 문제 파티 문제 바로가기 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라. 풀이 모든 점에서 X까지의 시간과 X에서 모든 점까지..