인문학적 공학도

4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 www.acmicpc.net 오랜만에 BFS 문제를 풀어봤다. 요즘은 소마 코테를 준비하느라 브루트포스, DP, BFS 위주로 푸는 중이다. 각설하고, 입력된 그래프의 연결요소의 개수를 구하는 문제. 연결 요소란, '무향 그래프에서 ..

14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 구조는 간단하지만 상당히 까다로웠던 문제. 문제는 크게 두 부분으로 나뉜다. 1. 연구소의 벽 세우기 2. 바이러스 퍼뜨리기 처음에 문제를 접했을 때 완전탐색(브루트포스)를 숙지하지 않았기 때문에 벽을 어떻..