문제: www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제풀이 배열 board에서 입력으로 주어진 좌표 범위를 모두 1로 초기화하고 0인 부분을 BFS했다. 코드 #include #include #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int visited[100][100] = {0,}; int board[100][100] ..

문제: www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제풀이 이 문제에서 프로젝트 팀이라는 것은 그래프의 사이클을 뜻한다. 사이클에 속하지 못한 노드들의 개수를 구하는 문제이다. visited 배열을 선언해 0이면 방문하지 않은 노드, -1이면 사이클에 속하는 노드, 0과 -1이 아닌 다른 숫자이면 방문은 했으나 사이클에 속하지 못하는 노드를 뜻한다. 노드 하나하나를 모두 사이클에 속하는지 검사하면 시간 초과로 문제를 틀리게 된다. 때문에 한 번 방문할 때 연..

문제: www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제풀이 같은 이름의 7576번 토마토 문제와 다른 점은 토마토가 3차원으로 주어진다는 것이다. 3차원 배열에 대하여 BFS를 진행하여 최단거리를 구하면 된다. 이때 토마토(1)가 주어진 곳의 좌표는 토마토가 익을 수 있는 시작점이므로 큐에 push 해준다. 코드 #include #include #include using namespace std; int dz[6] = {-1,1,..

문제: www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제풀이 흰 배추 지렁이는 인접한 배추로 이동할 수 있으므로 서로 인접한 배추가 몇 군데 있는지를 알아내는 문제였다. BFS를 이용하여 방문하지 않은 배추를 찾을 때마다 카운트를 증가시켜 서로 인접한 배추가 몇 군데 있는지를 알아냈다. 코드 #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int board[50..

문제: www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 문제풀이 BFS를 이용한 최단거리 문제 거리 배열을 2개를 선언하고 배열 1은 불의 BFS 순서를 저장하고 배열 2는 지훈이의 BFS 순서를 저장하였다. 배열 2의 BFS 순서를 저장할 때 저장하기 전 배열 1의 값과 비교하여 배열 1의 값이 배열 2의 값보다 작거나 같으면 불이 붙어있거나 지훈이와 불이 동시에 도착할 수 있는 즉, 갈 수 없는 좌표이므로 continue 해준다. 코드 #i..

문제: www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제풀이 일차원 선 위에서 BFS를 이용하여 최단거리를 구하였다. 이때 수빈이와 동생의 위치는 0부터 100, 000까지이지만 수빈이는 현재 거리의 2배를 순간 이동할 수 있기 때문에 거리 배열을 100,000의 두배인 200,001로 선언하였다. 코드 #include #include using namespace std; int dist[200001]; int main(){ i..