작심 24/7

2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 삼차원 배열로 벽을 부수지 않은 경우, 벽을 부순 경우를 나누어 계산한다. 1. 벽을 부수지 않은 경우[0][x][y] 벽을 만났을 때 -> 벽을 한 번 부숴도 되므로 [1][x][y]에 값 넣음 벽을 만나지 않았을 때 -> [0][x][y]에 값 넣음 2. 벽을 부순 경우[1][x][y] 벽을 만났을 때 -> 두번 이상 부술 수 없으므로 값을 넣지 않음 벽을 만나지 않았을 때 -> [1][x][y]에 값 넣음 큐도 두 개로 나누어 ..

3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치�� www.acmicpc.net 백준 불 문제와 비슷한 문제이다. 모든 홍수 먼저 인접한 빈 곳을 찾아 *로 바꾸어주고 다음 검사를 위해 큐에 넣어준다. 그다음 고슴도치가 갈 수 있는 인접한 빈 곳을 찾아 그곳까지 가는데 걸린 시간 + 1을 넣어준다. 고슴도치가 D를 만나면 그때까지의 시간을 출력해주고 만나지 못했다면 KAKTUS를 출력한다. #include #include #include using namespace std; char forest[51][51]; queue flood, hedgehog..

5427번: 불 문제 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. www.acmicpc.net 모든 불을 먼저 인접한 빈 공간을 검사한 뒤 그 공간을 불로 바꿔준다. 그다음 내가 갈 수 있는 인접한 빈 공간을 찾은 뒤 이전 공간의 값(이전 공간까지 가는데 걸린 시간) + 1한 값을 넣어준다. 내가 갈 수 있는 빈 공간이 없는 경우는 IMPOSSIBLE이고 내 위치가 빌딩의 가장자리인 경우엔 그 시간을 출력해준다. #include #include #include #include using namespace std; int X, Y, x, y, suc..

6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 www.acmicpc.net 3차원 버전의 미로 탐색 문제이다. 출발지에서 시작하여 동, 서, 남, 북, 상, 하로 갈 수 있으면 +1된 값을 넣어준 뒤 큐에 그 위치를 넣어서 나중에 처리한다. 큐의 front가 출구면 그때까지의 값을 출력시키고 출구를 만나지 못하고 검사가 모두 끝나면 Trapped!를 출력시킨다. #include #include #include #include using namespace std; int success = 0, z, x, y, Z, X, Y; int dx[6]..

1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 기본적인 DFS와 BFS이다. DFS는 재귀로 구현하였고 BFS는 큐로 구현하였다. 방문할 수 있는 정점이 여러 개인 경우엔 번호가 더 작은 것부터 방문해야 하므로 벡터의 각 행마다 오름차순으로 정렬시켜주었다. #include #include #include #include using namespace std; vector v[1001]; queue q; int visited[1001] = { 0 }, idx; void Df..

7562번: 나이트의 이동 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 www.acmicpc.net 출발 위치에서부터 나이트가 갈 수 있는 8가지 위치의 값에 현재 위치의 값 +1을 넣어주고 (방문하지 않은 경우에만) 이 위치들을 큐에 넣어준다. 그렇게 큐의 front마다 탐색해주다 목표 위치를 만나게 되면 그만두고 출력시킨다. #include #include using namespace std; int dx[8] = { -1, -2, -2, -1, 1, 2, 2, 1 }, dy[8] = { -2, -1, 1, 2, 2, 1, -1, -2 }; int a, b..

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 각 위치까지 가는데 얼마나 걸리는지 저장하다가 그 위치가 N-1, M-1일 때 출력시키면 된다. 0,0부터 시작하기 때문에 i,j에 0,0부터 넣어주고 상하좌우를 검사하며 maze의 값이 1이고 방문하지 않은 곳인 x, y을 찾은 뒤 i, j의 값+1을 넣고 방문에 체크해주고 x, y를 큐에 넣어준다. 이 과정이 끝나면 큐를 pop시켜주고 front에 있는 값을 i, j로 만든 다음 반복한다. #include #include #include #include using namespace std;..

2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진� www.acmicpc.net BFS와 재귀로 풀었다. x, y의 촌수를 구해야 할 때 x를 루트로 잡고 x부터 y가 나올 때까지 BFS 해주었다. 만약 y를 만나지 못한다면 -1을 출력했다. 무방향 그래프이므로 입력받을 때 벡터[x]=y, 벡터[y]=x 둘 다 값을 넣어준다. BFS 해줄 때 다음 노드로 넘어갈 때마다 촌수를 +1 해주었고 현재 노드와 연결된 모든 노드들을 검사한 후(검사하는 노드마다 방문 체크) 검사가 다 끝나면 이전 노드로 돌아가기 전에 촌수를 -1 해주..