문제: www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 먼저 문제를 풀고 오시는 것을 추천드립니다. 문제분석 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었습니다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 합니다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있습니다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지합니다...

문제: 16236번: 아기 상어 (acmicpc.net) 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제를 먼저 풀고 오시는 것을 추천합니다. 이 문제의 풀이는 BFS 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다. 문제분석 문제에 아기상어에 대한 제한조건이 많은 편입니다. N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있습니다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있고 한 칸에는 물고기가 최대 1마리 존재합니다. 아기 상어와 물고기는 모두 크기..

문제 2667번: 단지번호붙이기 (acmicpc.net) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제를 먼저 풀고 오시는 것을 추천합니다. 이 문제의 풀이는 BFS 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다. 문제분석 1은 집이 있는 곳이며, 0은 집이 없는 곳을 나타냅니다. 상하좌우로 연결된 집들의 모임이 단지입니다. 각 단지에 속하는 집의 수를 센 다음 오름차순으로 정렬해야 합니다. 입력 첫번째 줄에 지도의 크기 N (5

문제 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제를 먼저 풀고 오시는 것을 추천합니다. 이 문제의 풀이는 BFS 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다. 문제분석 배추흰지렁이는 인접한 다른 배추로 상하좌우 이동할 수 있습니다. 배추가 모여있는 곳은 배추흰지렁이가 한 마리만 있으면 됩니다. 배추가 군데군데 모여있어서 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있습니다. 0은 배추가 없는 땅이고, 1..

문제: www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제를 먼저 풀고 오시는 것을 추천합니다. 이 문제는 제목에도 표현되어 있지만 DFS, BFS 알고리즘을 사용할 줄 아는지 물어보는 문제입니다. 문제분석 그래프를 DFS, BFS로 탐핵한 결과를 출력하라는 문제입니다. 단, 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것부터 방문하시면 되고 더이상 방문할 수 있는 점이 없으면 종료하면 됩니다. 이번 그래프..

문제 www.acmicpc.net/problem/1325 1번 컴퓨터 순으로 신뢰한다고 생각해보겠습니다. 그러면 5번 컴퓨터를 해킹하면 더 이상 해킹할 수 있는 컴퓨터가 없으면 ⑤ = 0 입니다. 3번 컴퓨터를 해킹하면 3을 신뢰하는 5번 컴퓨터를 해킹할 수 있으므로 ③ = 1 입니다. 1번 컴퓨터를 해킹하면 3을 해킹할 수 있고 3번 컴퓨터를 신뢰하고 5까지 해킹할 수 있습니다. 따라서, ① = 2입니다. 예제풀이 백준온라인 문제의 예제에서 나온 번호를 그래프로 그려보면 이렇게 나옵니다. 신뢰하는 관계를 방향대로 읽어가면서 해킹가능한 수를 하나씩 더하면 각 컴퓨터별로 동시에 해킹할 수 있는 개수가 나옵니다. 각 컴퓨터 번호별로 동시에 해킹할 수 있는 수는 제가 소스에서 주석처리를 풀면 확인할 수 있도록..