작심 24/7

9029번: 정육면체 입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20) 가 주어진다. 각 테스트 케이스에 대해 원목의 크기를 나타내는 W,L,H (1 ≤ W, L, H ≤ 200) �� www.acmicpc.net 규칙을 찾으면서 너무 어렵게 생각하려고 하면 풀기 힘든 문제이다. DP로 W, L, H가 1, 1, 1일 때부터 200, 200, 200일 때까지 값을 모두 구해놓고 풀어야 한다. 설명하자면, 이렇게 그림에 나와있는 것처럼 직육면체를 두 조각으로 자르는 것에 주목해보자 H를 1 기준으로 자른 조각들은 W, L, 1와 W, L, H-1가 되고 W, L, 1에서 얻을 수 있는 정육면체의 최소 개수와 W, L, H-1에..

2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 � www.acmicpc.net 안전한 영역의 개수 중 최댓값을 출력하는 문제이다. 먼저 입력받을 때 높이 중 최대 높이를 구한 후 높이 1부터 최대 높이까지 비교해야 한다. 원래 이런 BFS문제들을 풀 때 입력 배열의 비교가 끝나면 값을 0으로 만들어주었지만 이번엔 한 입력 배열로 여러 번 비교해 줘야 하기 때문에 따로 visited 배열을 만들어서 방문 여부를 체크해준다. BFS의 원리는 현재 위치(큐의 front)를 기준으로 상하좌우를 비교해 주는데 안전한 영역일 때인 현재 위치의 높이(ar..

10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G( www.acmicpc.net 처음엔 두 가지의 버전의 BFS를 만들었다가 애초에 입력받을 때 R과 G를 통일을 해주면 BFS함수 하나만으로도 풀 수 있다는 걸 깨달았다. 이차원 배열 두 가지를 만들어 하나는 정상적으로, 하나는 R과 G를 R로 통일해준다. BFS함수는 늘 짜던 그 방식으로 해주면 된다. #include #include using namespace std; int daltonism = 0, non_daltonism = 0, x, y; void Bfs(..

11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 모든 정점을 둘러보며 현재 정점이 가리키는 정점을 다시 현재 정점으로 삼는 방식으로 재귀로 DFS를 구현했다. 한 번 방문한 정점은 visited로 표시해준 후 다시는 방문하지 않도록 해주었다. 한 정점의 연결고리 검사가 모두 끝나면 visited를 0으로 다시 초기화해주고 그다음 정점의 연결고리들을 모두 검사해준다. #include using namespace std; void Dfs(int N, int idx, int graph[][101], int visited[]) { for (..

2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 같은 단지인 애들을 BFS로 찾아준 다음 집의 수를 카운트 해주고 단지 배열에 넣어준다. 이차원 배열을 돌면서 값이 1인 곳이 있으면 그걸 시작으로 해당 위치의 상하좌우의 값이 1이면 큐에 그 위치를 넣어놓고 큐가 empty할 때까지 반복해주는 BFS함수를 만들면 된다. #include #include #include #include using namespace std; int cnt = 0, town[625] = { 0 }; void Bfs..

1743번: 음식물 피하기 문제 코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있� www.acmicpc.net 백준 유기농 배추와 거의 같은 문제이다. 그룹들 중 가장 큰 그룹을 bfs로 찾아 출력하면 된다. BFS는 현재 위치의 상하좌우가 1이면 큐에 넣고 큐가 빌 때까지 계속 반복해서 비교하도록 만들면 된다. #include #include #include using namespace std; int Max = 0; void Bfs(int i, int j, int N, int M, int arr[][101]) { int cnt = 1; queue q; q..

11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 무방향 그래프 이므로 u와 v를 입력받으면 벡터[u]=v, 벡터[v]=u 를 넣어준다. 벡터가 empty될 때까지 방문하지 않은 곳만 DFS로 탐색해주고 한 번이라도 방문한 곳은 visited로 표시해준다. 여기서 주의할 점은 간선을 가지지 않는 정점도 하나의 연결 요소로 취급하므로 먼저 벡터가 empty인 애들의 수부터 전부 카운트 해주는 것이 포인트이다. #include #include usin..

9466번: 텀 프로젝트 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 www.acmicpc.net DFS로 풀 수 있는 문제이다. 팀이 구성되는 경우는 사이클이 생기는 경우라 생각하면 된다. 사이클이 생기는 경우를 찾아주기 위해 current와 visited 배열이 필요하다. current엔 stack에 들어가 있는 애들을 표시해주고 visited는 비교가 끝난 애들을 체크해준다. 사이클이 생기는 경우엔 사이클의 시작과 끝을 담당하는 애를 leader에 넣어주고 current를 참고하여 사이클이 형성되는 부분까지는 팀이 구성되는 걸로 간주하여 카운트 값을 하나씩 ..