우노

문제 로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다. 로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동합니..

문제 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은..

문제 NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다. 시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다. 시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과..

문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 ..

문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자. 이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다. 입력 조건 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다..

문제 N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입력 조건 첫째 줄에 두 정수 N, M(4 = 0 and ny < m): # 인접한 노드를 방문할 수 있는지 확인 if (check[nx][ny] == 0 and maze[nx][ny] == 1): # 방문할 수 있다면 큐에 삽입 queue.append((nx,ny)) ..

문제 링크 https://www.acmicpc.net/problem/3055 풀이 문제 목표 고슴도치가 비버 소굴까지 안전하게 갈 수 있는, 최소 시간을 구하는 것입니다. 중요 사항 입력 받는 물의 시작 위치는 여러 곳일 수 있습니다. 물과 고슴도치는 매 분마다, 상하좌우로 비어있는 곳을 찾아 확장됩니다. 다음턴에 물이 채워지는 곳은 고슴도치가 이동할 수 없습니다. 풀이 방법 물을 먼저 확장시킨 뒤, 고슴도치를 이동시켰으며, 지도에서, 물이 확장되는 곳은 ‘*’ 로, 고슴도치가 이동하는 곳은 ‘S’ 로 변경하며 진행했습니다. 첫 번째 예제 입력에 따른 진행 과정 3 3 D.* ... .S. D** .S* SSS D** SS* SSS 두 번째 예제 입력에 따른 진행 과정 3 3 D.* ... ..S D**..

문제 링크 https://www.acmicpc.net/problem/2178 풀이 중요 내용 (0, 0) 에서 (N-1, M-1) 까지의 최소 칸수를 구하는 문제 최단 경로 탐색 시, 현재까지 이동한 칸의 개수를 저장해나가며 탐색하는게 중요하므로, 이동한 칸의 개수를 2차원 배열에 저장하며 진행 탐색은 상하좌우로만 진행하며, 아직 방문하지 않았고, 이동 가능한 칸일 경우에만 이동함 좌측 미로를 BFS 탐색할 경우, 이동칸 결과는 우측과 같음 코드 #include #include #define MAX 101 using namespace std; int N, M; // 미로 크기 int maze[MAX][MAX]; // 미로 표현용 2차원 배열 int visited[MAX][MAX]; // 방문 기록용 2차..

문제 링크 https://www.acmicpc.net/problem/1260 풀이 DFS 는 한 노드에서 인접한 노드를 발견하면, 그 즉시 발견한 노드에 대해 DFS 함수를 실행하는 방법으로 구현했습니다. BFS 는 재귀가 아닌, Queue 를 이용한 반복문으로 구현했습니다. Queue 의 front 노드를 출력한 뒤, front 노드와 인접한 노드 중 아직 방문되지 않은 노드를 Queue 에 새롭게 추가하고, front 노드를 삭제합니다. Queue 안에 노드가 없을때까지 반복합니다. 코드 #include #include #define N 1001 using namespace std; // N : 정점의 개수, M : 간선의 개수, V : 탐색 시작 정점 int n, m, v; // f_node : 연..