이 험난한 세상에서어어~

문제 풀이 https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 1부터 N까지 노드가 있을 때 해당 숫자와 연결된 배열이 주어진다. 여기서 순열 사이클의 수를 찾는 문제이다. 문제 풀이 첫 번째 풀이 처음에는 간단하게 반복문으로 풀어줬다. 시작하는 노드 start와 그래프를 탐색하면서 변하는 현재 노드 current, 그리고 현재 노드와 연결된 다음 노드 next를 이용했다. ..

문제 설명 nxn 모양의 바둑판이 있다. 이때 (0, 0)에서부터 (n-1, n-1)까지 가려고 한다. 다만, 검은 방이 존재하여 갈 수 없을지도 모른다. 때문에 (0, 0)에서부터 (n-1, n-1)까지 갈 수 있으면서 검은 방을 최소한 하얀 방으로 만드는 그 수를 구하여라 https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 문제 풀이 잘못된 풀이 문제를 본 처음에는 검은 방을 0부터 검은 방의 수 만큼까지 조합으로 만들어서 하얀방을 표시한 다음..

문제 설명 nxm 칸에 구멍이 있는 치즈가 하나 놓여 있다. 공기와 닿은 칸이 1시간 지나면 녹게 되는데, 치즈의 구멍에는 칸이 없지만 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. 이때 치즈가 다 녹는 시간과 마지막 시간에 남은 치즈의 수를 구하여라 https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 문제 풀이 언뜻 보면 쉬워 보이지만, 문제를 파악할 때 함정이 있는데 바로 탐색의 중심을 치즈가 아닌 공기로 잡아야 한다는 것이다. 나는 처음에 치즈를 ..

문제 설명 파이프를 옮겨 (n, n) 칸 까지 갈 수 있는 경우의 수가 총 몇 가지인지를 묻는 문제이다. 이때, 초반의 파이프는 무조건 (1, 1)과 (1, 2)를 차지하고 있고 총 세 가지 방향으로 움직일 수 있다. 파이프가 움직일 수 있는 방향은 오른쪽, 아래, 오른쪽 대각선 아래인데 이때 파이프는 45도 방향으로만 회전시킬 수 있다. 그렇기에 오른쪽 방향 파이프는 오른쪽 혹은 오른쪽 대각선 아래로만, 아랫 방향 파이프는 아래 혹은 오른쪽 대각선 아래로만, 오른쪽 대각선 아래 방향 파이프는 전부다 가능하다. https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의..

문제 설명 NxN 크기의 종이가 있고 각 칸에는 -1, 0, 1로 표시가 되어 있다. 같은 숫자가 표시되어 있는 영역을 하나의 종이로 보는데, 만일 숫자가 모두 같지 않다면 해당 종이를 9등분 한 다음 9등분 한 영역을 다시 확인한다. 결과적으로 -1로만 채워진 종이의 수, 0으로만 채워진 종이의 수, 1로만 채워진 종이의 수를 구하여라. https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 풀이 분할 정복 문제로 나는 재귀를 이용하..

문제 설명 각 지역의 높이가 주어지고 비가 내렸을 때 잠기지 않은 지역의 최대값을 구하는 문제이다. 부르트 포스로 전체 물의 양을 확인해서 구하고 물에 잠기지 않는 지역은 BFS로 풀면 된다. 다만, 전체 지역이 물에 잠기지 않을 수 있으니(지역의 모든 높이가 일정한 경우) 이 경우만 주의하면 된다. 문제 풀이 1. raining() 메소드로 잠긴 지역을 체크한다. 이때 비의 양의 범위는 주어진 높이의 최솟값부터 최댓값 사이이다. 나는 0부터 돌리지는 않았는데, 그 이유는 최솟값보다 작으면 어차피 잠기는 곳이 없기 때문이다. 2. 잠긴 곳을 표시했으면 BFS를 돌려서 잠기지 않은 지역을 세주면 된다. 지금까지 풀어왔던 BFS 문제와 동일하게 해주면 된다. 3. 그리고 잠기지 않은 지역의 수가 현재의 an..