code/BOJ (63) 썸네일형 리스트형 백준 16946 벽 부수고 이동하기 4 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. 각각의 벽에 대해서 다음을 구해보려고 한다. 벽을 부수고 이동할 수 있는 곳으로 변경한다. 그 위치에서 이동할 수 있는 칸의 개수를 세어본다. www.acmicpc.net 맵의 크기가 10^6이고, 최악 매번 10^6만큼 탐색을 수행하면 10^12이고, 10^9를 초과한다. 벽을 시작점으로 빈칸을 탐색하면 중복 연산이 발생한다. 이를 방지하기 위해서는 빈칸을 시작점으로 빈칸을 탐색하여 빈칸 그룹들의 크기를 산출한다. -> 10^6 벽마.. 백준 14502 연구소 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 안전 영역의 크기를 구하는 공식을 잘못 구했다. 빈칸의 개수에서 추가된 벽의 개수(3)와 확산된 바이러스의 개수를 빼면 안 된다. DFS에서 거쳐간 모든 바이러스의 개수가 빠지고, 확산되기 전 바이러스도 포.. 백준 1290 배럭 1290번: 배럭 첫재 줄에 상대방의 배럭을 파괴시키고, 상대방의 마린을 모두 죽이려고 할 때, 필요한 최소 턴의 수를 출력한다. 불가능한 경우에는 -1을 출력한다. www.acmicpc.net loop fision을 시도했지만 적용 불가한 문제로 판명되었다. #include using namespace std; intN, B, U, M, TU, t; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> B >> U; for(t = 1; ; ++t) { B -= N; N -= TU; if (B > 0) { TU += U; } else { break; } } TU += B; for (; TU > 0 && N > 0; .. 백준 1011 Fly me to the Alpha Centauri 로그인 www.acmicpc.net #include using namespace std; int T, x, y; unsigned int sq[46343]; int main() { for (int i = 0; i > T; while (T--) { cin >> x >> y; int n = y - x; for (int i = 0; i = n) { if (sq[i - 1] + i - 1 >= n) { cout 백준 1559 놀라운 미로 1559번: 놀라운 미로 문제 MxN개의 칸으로 구성된 미로가 있다. 각 칸에는 4개의 인접한 곳으로 이동할 수 있는 문이 있다. 이 4개의 문은 한 번에 한 개만 열리며, A에서 B로 가는 문과 B에서 A로 가는 문은 별개로 작동한다. 문들의 초기 상태는 입력에서 주어지며, 1분에 한 번 시계 방향으로 90도씩 바뀐다. 미로에는 총 K개의 보물상자가 있다. 당신은 1분에 문이 열린 방향으로 한 칸 움직이거나 원하는 방향의 문이 열릴 때까지 기다릴 수 있다. 미로에서 당신이 시작 www.acmicpc.net vst 차원을 2개 추가해야 했는데 문이 열리는 방향의 회전 주기 4의 차원이 그 중 하나다. 주기이므로 src 다음 지점은 src + 1 값으로 vst 처리를 해야 한다. src 다음 지점을 vst.. 백준 4179 불! 4179번: 불! 문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다. 불은 각 지점에서 네 방향으로 확산된다. 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 지훈이와 불은 벽이 있는 공간 www.acmicpc.net #include #include #include using namespace std; int R, C; string str; int maze[1000][1000];// 0 : 무, 1 : 지훈 기방문, 2 : 불,.. 백준 17779 게리맨더링 2 문제: 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다 www.acmicpc.net 코드: #include #include #include #define f(i, n) for(int i = 0 ; i < (n); ++i) #define IN(r, c) (0 map[r][c.. 백준 17471 게리맨더링 문제: 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 코드: /* 1. 마을 번호 1부터 시작! */ #include #include #include using namespace std; int N; int pop[10]; vector adj[10]; bool perm[10]; bool side; int sz[2], sum[2]; bool vst[10]; int dif; int ans = 1000; void DFS(int v) { vst[v] = 1; for (auto w : adj[v]) { if (vst[w] || perm[w.. 이전 1 2 3 4 5 6 7 8 다음
