문제: www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제풀이 BFS 알고리즘 문제이다. 큐와 방문여부배열, 영역개수를 2개씩 선언하여 하나는 색약이 아닌 사람 다른 하나는 색약인 사람의 영역 개수를 구하였다. 코드 #include #include #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int visited1[100][100] = {0..

문제: www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제풀이 브루트포스와 BFS 알고리즘을 이용하여 문제를 풀었다. 비의 높이(h)에 대하여 h보다 높이가 높은 지대의 인접한 땅들의 영역 개수를 BFS로 구한다. 이때 h가 0부터 100일 때까지의 경우의 수 모두 비교한다. 코드 #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int board[100][1..

문제: www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제풀이 각 영역의 넓이를 구하여 오름차순으로 출력하는 문제이다. BFS를 이용하여 각 구역에 대하여 탐색하고 그 넓이를 각각 벡터에 저장하였다. 벡터를 sort() 함수를 이용해 오름차순 정렬시킨 후 출력하였다. 코드 #include #include #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; ..

문제: www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제풀이 BFS를 이용하여 최단거리를 구하는 문제이다. 다른 너비우선탐색과 다르게 dx, dy가 상하좌우가 아닌 나이트 말이 움직일 수 있는 수로 고쳐주면 된다. int dx[4] = {-1,1,0,0} --> int dx[8] = {-2,-2,-1,-1,1,1,2,2} int dy[4] = {0,0,-1,1} --> int dy[8] = {-1,1,-2,2,-2,2,-1,1} 코드 #include #in..

문제: 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이 아닌 다른 숫자이면 방문은 했으나 사이클에 속하지 못하는 노드를 뜻한다. 노드 하나하나를 모두 사이클에 속하는지 검사하면 시간 초과로 문제를 틀리게 된다. 때문에 한 번 방문할 때 연..