문제 (링크)17142번: 연구소 3 (acmicpc.net) 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 사고과정 먼저 4방향으로 퍼지고, 퍼지는데 걸리는 총 시간을 구하는 것이므로 bfs(queue)를 이용해야한다. 그리고 바이러스중 활성바이러스로 만들 것을 고르는 것은 N중 반복문이나 재귀함수를 사용하면 되는데 고르는 수가 변수이므로 재귀함수를 이용하면 편할 것이다. 그리고 각 경우 중 가장 짧은 소요시간을 구하는데, 어떤 경우에도 모든 칸을 확산시키지 못하면 -1을 출력해야 하므로 각 경우마다 전체 맵을 탐색..

문제 (링크)17143번: 낚시왕 (acmicpc.net) 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 사고과정 처음 문제를 접할 땐 문제를 푸는 방법 자체는 그리 어렵지 않을 거라 생각했다. 하지만 상어의 정보를 어떤식으로 저장하느냐가 관건이었다. 그래서 나는 map에 상어의 이름을 저장하고, 그 상어의 이름을 index로 하는 구조체 배열에 상어의 정보를 저장했다. 이렇게 하면 map을 전체 탐색하지 않고 상어의 개수만큼만 탐색할 수 있기 때문이고, 필요없는 메모리 사용을 줄일 수 있..

문제 (링크)17144번: 미세먼지 안녕! (acmicpc.net) 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 사고과정 문제에서 요구하는대로 먼지확산 -> 공기순환의 과정만 조건대로 구현하면 된다. 그래서 사용한 함수는 2개! 처음엔 탐색횟수를 줄이기 위해 먼지의 위치를 저장하는 배열을 만들까 했는데, 빈공간으로도 먼지가 확산되기 때문에 map전체를 탐색하는 것이 마음이 편할 것 같았다. 내코드 #include #include #define FRESHER -1 int width, height, time;..

문제 (링크)16236번: 아기 상어 (acmicpc.net) 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 사고과정 문제를 풀때 어떻게 접근할까 생각을하는데 조금 애먹은 문제다. 중 에 위치한 물고기를 먼저 먹으라는 조건이 있기 때문이다. 먼저, 최단 거리를 우선으로 찾으려면 bfs를 사용하는 것이 좋다. 현재 상어의 위치로부터 거리순으로 탐색할 수 있기 떄문이다. 대신 같은 거리에 존재하는 물고기가 여러마리면 위/왼쪽 방향의 물고기를 먼저 먹는다고 했으니 그 부분도 고려해줘야 한다. 최대한 피요없는..

문제 (링크)16234번: 인구 이동 (acmicpc.net) 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 사고과정 먼저 생각해야할 것은 현재 각 나라의 인구 상태에서 연합이 만들어질 수 있는가이다. 이후 visit배열에 형성된 연합끼리 정보를 달리한 뒤 인구를 분배하면 된다고 생각했다. 그런데 코드를 짜다보니 굳이 연합이 가능하지 탐색하는 것과, 연합을 만든다음 인구를 분배하는 과정을 분리할 필요가 없다는 것을 깨달았다. 내코드 #include #include typedef struct { ..

문제 (링크)15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 사고과정 문제에서 입력이 그래프를 활용할 수 있도록 주어져서 조금 흠칫했다. 하지만 문제에서 요구하는 것은 각 집에서 선택한 치킨집까지의 거리중 최소거리를 합한 것이므로, 각 좌표의 정보를 순차적으로 담기만 하면 된다. 이후 집의 좌표와 치킨집의 좌표를 따로 저장하고, 재귀함수를 통해 치킨집을 골라내면 된다. 내코드 #include #define HOUSE 1 #define CHI..