문제 문제 바로가기> BOJ 2933번: 미네랄 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 풀이 옛날에 풀다가 때려쳤었는데,, 오랜만에 싹 지우고 다시 풀어봤다! 중력을 작용시키는 클러스터를 찾는 부분, 중력을 처리하는 부분만 주의해주면 된다! 클러스터가 지면에 닿아있지 않다면, 중력이 작용하는 클러스터이다! #include #include #include #define MAX 101 using namespace std; struct POS{int y, x;}; vector cluster; int R, C, N; ch..
문제 문제 바로가기> BOJ 16724번: 피리 부는 사나이 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 풀이 dfs 탐색을 통해 이동을 진행하다가, 해당 턴에서 이미 방문했던 곳으로 돌아오는 경우, SAFE ZONE이 필요한 것이므로 ans를 1증가해주었다! #include #include #define MAX 1001 using namespace std; int N, M, ans=0; char map[MAX][MAX]; int visited[MAX][MAX]; void..
문제 문제 바로가기> BOJ 2842번 : 집배원 한상덕 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net 풀이 고도를 ±1 씩 모든 경우의 수를 구할 경우 시간 초과가 발생한다. 50*50*1,000,000 = 2,500,000,000 (25억,,) 하지만 실제 고도의 개수는 50*50 = 2500을 초과할 수 없고, 이를 반영해서 "투 포인터 + 그래프 탐색"으로 풀었다. 1. 투포인터를 이용하기 위해 고도를 정렬해야 한다. 이때, 중복되는 값은 필요 없으므로!! set을 이용해서 중복되는..
문제 문제 바로가기> BOJ16946번: 벽 부수고 이동하기 4 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 매번 벽을 만날 때마다 dfs 혹은 bfs 탐색을 진행하면, 복잡도가 O(N^2*M^2)이고, N과 M 은 최대 1000이므로, 시간초과가 발생한다! 이동 가능한 곳의 영역을 미리 체크해 놓는다면, 시간 복잡도를 O(N^M)으로 줄일 수 있다. 예를 들어 예제 2번의 경우, 4 5 11001 00111 01010 10101 다음과 같이 이동가능한 영역의 size?를 미리 체..
문제 문제 바로가기> BOJ 17472번: 다리 만들기 2 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 1. 섬 (2 ≤ 섬의 개수 ≤ 6) 에 대표 번호? 를 매겨주었다. 어떤 섬에서 어떤 섬으로 이어지는 다리인지 알기 위해서! 2. 문제에서 준 조건인, ▷ 다리의 길이 > 2 ▷ 중간에 방향 변화 불가 를 만족 시키는 다리(edge)가 이어주는 섬 두개 (from, to), 다리 길이(len)를 pq에 넣어준다! 이 때, 상 하 좌 우 탐색을 모두 진행하면, 중복되는 edge들..
문제 문제 바로가기> BOJ 16234번: 인구이동 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 문제의 요구사항을 구현해주면 되는 간단한 문제였다. 1. 연합을 구하기 위해 그래프 탐색 (DFS or BFS) 진행 2. 연합의 크기 > 1 인 경우, 인구 이동 연합의 크기 < 1 인경우, break ; 정답 출력 크게 위와 같은 2가지 과정으로 이루어지는데, 연합을 구하기 위해 DFS를 사용했을 때가 BFS를 사용했을 때 보다 시간이 훨씬 줄어들었다. 그 이유를 찾아보니 ... DFS함수..
문제 문제 바로가기> BOJ 17070번: 파이프 옮기기1 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 DFS 탐색을 통해 간단하게 해결할 수 있는 문제다! 1. 파이프의 마지막 부분(초기값 : (1,2))을 추적해가면서 DFS 탐색 진행 (가로, 세로, 대각선 이동 방법이 다름) 2. 종료 조건 : 범위를 벗어나는 경우, 빈칸이어야하는 부분인 벽인 경우 (범위를 벗어나는 경우를 확인할 때, N보다 큰지만 확인해주면 된다. 더하는 방향으로만 이동하기 때문!) 3. (N, N)에..
문제 문제 바로가기> BOJ 14502번: 연구소 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 벽 3개를 놓을 수 있는 모든 조합의 경우를 고려해서, 안전 영역의 최대 크기를 구해 주면 된다! C++ #include #include #define MAX 9 #define EMPTY 0 #define WALL 1 #define VIRUS 2 using namespace std; int N, M; int ans = 0; int lab[MAX][MAX]; int copy_lab[MAX][MAX]; int dy[] = {..
문제 문제 바로가기> BOJ 2573번: 빙산 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 dfs를 사용하여 빙하가 분리되었는지 확인해주는 방식으로 문제를 풀었다! #include #include #define MAX 301 using namespace std; int N, M; bool allmelt; int arr[MAX][MAX]; int copy_arr[MAX][MAX]; bool visited[MAX][MAX]; int dy[] = {-1, 1, 0, 0}; int dx[] = {0, ..
문제 문제 바로가기> BOJ 1260번: DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 DFS와 BFS를 구현할 수 있는지를 보는 간단한 문제이다. 주의해야할 점은 "정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문"하기 때문에 미리 연결되는 node를 정렬해 두어야한다는 것이다! #include #include #include #include #define MAX 1001 using namespace std; int N, M, V; bo..