JArchive 프로그래밍 일기

목차 

0x00 재귀 알고리즘 설명 

0x01 연습문제1 - 거듭제곱

0x02 연습문제2 - 하노이 탑 

0x03 연습문제3 - Z

0x00 재귀 알고리즘 설명 

재귀를 이해하고 문제를 푸는 것은 익숙해지기에 시간이 좀 걸린다.

순서대로 생각하는 절차지향적 사고와는 차이가 있기 때문이다. 마음 단단히 먹고 시작하기. 

재귀란? 

하나의 함수에서 자기 자신을 다시 호출해 작업하는 알고리즘이다. 

재귀로 N부터 1까지 출력하는 함수와, 1부터 N까지 합을 구하는 함수를 혼자 구현해보자. 

[ N부터 1까지 출력하는 함수 ]

void printrec(int num){
  if(num == 0) return;
  cout << num << ' ';
  return printrec(num-1);
}
// 출력: 10 9 8 7 6 5 4 3 2 1

[ 1부터 N까지 합을 구하는 함수 ]

int rec(int num){
  if(num == 1) return num;
  return rec(num-1) + num;
}
// rec(n); 
// 출력: 55

(바킹독님 코드와 똑같아서 내코드 그대로 적어놓음)

재귀로 푼다는 것의 의미가 뭘까? 

방금 짠 재귀 코드가 왜 올바른 결과를 주는지 제대로 이해해보자. 

우리가 어떤 문제를 재귀로 푼다는 것은 곧 귀납적인 방식으로 문제를 해결하겠다는 것이다. 

아래 사진의 도미노 사진을 보자. 맨 앞의 1번 도미노를 쓰러뜨리면 모든 도미노가 쓰러진다. 

왜 그렇게 되는지 설명하는 방법에는 두 가지 방법이 있다. 

첫 번째 방법
1번 도미노가 쓰러지면 2번 도미노가 쓰러진다. 2번 도미노가 쓰러지면 3번 도미노가 쓰러진다. 3번 도미노가 쓰러지면 ... 

두 번째 방법 (수학적 귀납법)
'1번 도미노가 쓰러진다. '
'k번 도미노가 쓰러지면 k+1번 도미노가 쓰러진다' 
이 두 문장은 참이다. 그러므로 1번 도미노가 쓰러지면 모든 도미노가 쓰러진다. 

즉, 우리에게 익숙한 절차지향적인 사고를 탈피해야 귀납법에 익숙해질 수 있다. 

N부터 1까지 출력하는 함수를 귀납법으로 생각해보자

void func1(int n){
  if(n == 0) return;
  cout << n << ' ';
  func1(n-1);
}
// func1(3)  출력: 3 2 1

우선 절차지향적으로 func1(3)의 출력 결과가 왜 3 2 1 인지 생각해보자. 

코드의 흐름을 그대로 따라가면 된다. 

func1(3) 이 호출되면 3을 출력한다. 그리고 func1(2) 를 호출한다. 

-> func1(2)이 2를 출력한 후, func1(1) 호출한다. 

-> func1(1)이 1을 출력한 후, func1(0)을 호출한다. 

->  func1(0)이 호출되어 return 함수가 종료된다. 

귀납적 사고로 이해해보자.

첫 째로, func1(1)이 1을 출력한다. 이건 굉장히 자명하다.

그 다음이 관건인데,

func1(k)가 k, k-1, k-2 ... 1을 출력하면, 즉 k부터 1까지 차례로 출력하면 

func1(k+1)은  k+1부터 k, k-1, k-2 ... 1 까지 차례로 출력한다는 것을 보여야한다. 

이를 위해 func1(k+1)이 호출될 때 어떻게 되는지 확인하면 된다. 

func1(k+1)을 호출하면, k+1을 출력하고 func1(k)를 호출한다. 

그리고 func1(k)는 k부터 1까지 차례로 출력하는 가정을 했으니  func1(k+1)은 k+1부터 1까지 차례로 출력함을 알 수 있다. 

이 두 문장이 참이므로 귀납적으로 func1함수가 n부터 1까지 차례로 출력하는 함수임을 알 수 있다. 

재귀 함수의 조건

앞의 예시를 통해 귀납법에 익숙해지길 바라며 재귀 함수의 조건을 알아보자. 

올바른 재귀 함수는 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료해야 한다. 

이러한 입력을 base condition (==base case)라고 한다. 

그리고 모든 입력은 base condition으로 수렴해야 한다. 

int func2(int n){
  if(n == 0) return 0;
  return n+func2(n-1);
}

위 코드는 n==0 일 때, 자기자신을 호출하지 않고 종료된다. 이것이 base condition이다. 

그리고 이 함수에 자연수만 넣을 테니 모든 입력은 결국엔 n==0으로 수렴하게 된다. 

이 두 조건을 지키지 않으면 무한루프에 빠져서 런타임 에러가 발생한다.

재귀 함수의 조건과 정보

1. 재귀 함수의 인자, 로직, 종료 조건을 명확하게 정의해야 한다. 

2. 재귀는 코드를 간결하게 만들어줄 수 있지만, 메모리/시간에서는 손해를 본다는 것을 인지하자. 

굳이 재귀를 쓰지 않아도 구현이 된다면 반복문으로 코드를 짜는 것이 좋다. 

3. 한 함수가 자기 자신을 여러번 호출하게 되면 비효율적일 수 있다. 

아래 코드는 피보나치 함수다.

int fibo(int n){
  if(n <= 1) return 1;
  return fibo(n-1) + fibo(n-2);
}

fibo(5)는 fibo(4)와 fibo(3)을 호출한다. 

fibo(4)는 fibo(3)과 fibo(2)를, fibo(3)은 fibo(2)와 fibo(1)을 호출한다. 

-> 이미 계산한 값을 또 계산하게 된다!

-> 시간 복잡도가 말도안되게 커져버린다. 

-> 나중에 다이나믹 프로그래밍으로 O(n)에 해결하는 방법을 배운다. 

4. 재귀 함수가 자기 자신을 부를 때 스택 영역에 계속 누적된다. 

운영 체제의 메모리 공간을 보자. 제일 높은 주소 쪽에 컴파일 타임에 크기가 결정되는 stack 영역이 있다. 

stack영역은 지역변수와 함수의 호출정보(stack frame)가 저장되는데, 함수가 종료 되야 소멸한다. 

문제를 풀 때 메모리 제한이라는 것이 있다. 

일부 컴파일 환경에는 stack영역 메모리 제한이 별도로 1MB로 제한되어 있기도 한다. 

BOJ는 스택 메모리의 제한이 없지만 swexpertacademy.com에는 제한이 걸려 있다. 

그래서 이 코드 처럼 재귀를 10만번 정도만 돌아도 스택 1MB를 초과하여 런타임 에러가 발생한다. 

BOJ에 제출하면 "맞았습니다."가 뜨는 남의 코드를 로컬에서 돌렸을 때 계속 런타임 에러가 뜬다면, 

가장 의심해 볼만한건 재귀가 너무 깊거나 지역변수로 지나치게 큰 크기의 배열을 잡았을 경우다. 

0x01 연습문제1 - 거듭제곱

a의 b제곱을 m으로 나눈 나머지를 구하자. 

int func1(int a, int b, int m){
  int val = 1;
  while(b--) val *= a;
  return val % m;
}

방법1

a를 b번 곱한다. 그 결과를 m으로 나눈 나머지를 출력한다. 

하지만 '방법1'은 제대로 동작하지 않는다. 만약 func1(6, 100, 5)를 넣으면 0이 나온다. 

이유를 고민해보자.

.........

using ll = long long;
ll func1(ll a, ll b, ll m){
  ll val = 1;
  while(b--) val = val * a % m;
  return val;
}

그 이유는 바로 int overflow가 발생하기 때문이다.

6의 100제곱은 int의 범위를 까마득하게 벗어난다. 이것을 해결해주려면 중간 중간 계속 m으로 나눠서 나머지만 챙겨가면 된다. 

방법2

a를 1번째 곱한다. m으로 나눈 나머지를 a에 대입한다. 

a를 2번째로 곱한다. m으로 나눈 나머지를을 a에 대입한다. 

.... a를 b번째 곱한다. m으로 나눈 나머지를 출력한다.  -> 이렇게 중간 계속 m으로 나눠서 나머지만 챙기기.

a를 b번 곱하는 방식으로는 계산할 수 없다면 어떻게 할까? 

백준 1629번 곱셈 문제를 풀어보자. 

자연수 A, B, C가 주어진다. A를 B번 곱한 수를 C로 나눈 나머지를 출력하라. 

(A, B, C는 모두 2,147,483,647 이하의 자연수이다. 시간제한 0.5초)

힌트를 읽어보자. 

a의 n승을 제곱하면 a의 2n승이 된다. 

12의 58승과 12의 116승의 관계를 보자. 

12의 58승을 67로 나눈 나머지가 4라면, 12의 116승을 67로 나눈 나머지는 (4의 제곱) 즉, 16이 된다. 

-> 58승을 계산할 수 있으면 116승을 계산할 수 있다. 

-> k승을 계산할 수 있으면 2k승과 2k+1승도 O(1)에 계산할 수 있다. 

이 두 문장은 참이다. 따라서 a의 임의의 지수승을 귀납적으로 계산할 수 있다. 

귀납법의 일부를 코드로 바꿔보자. 

func(a, b, c)는 func(a, b/2, c)를 기반으로 구할 수 있다. 

using ll = long long;

ll func(ll a, ll b, ll c){
	val = func(a, b/2, c);
	val = val * a % c; // a를 곱하고 c로 나눈 나머지
}
// func(a, b, c)는 func(a, b/2, c)를 기반으로 구할 수 있다.

만약 b가 짝수라면 val을 그대로 리턴한다. 

만약 b가 홀수라면, "곱하기 a 하고 c로 나눈 나머지"를 한 번 더 수행한다. 

아래는 완성된 풀이코드다. 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll A, B, C;

ll rec(ll a, ll b, ll c){
  if(b == 1) return a % c; // a가 c보다 클 수 있기 때문에 a % c를 반환.
  ll val = rec(a, b/2, c);
  val = val * val % c;
  if(b%2 == 0) return val; 
  return val * a % c; // b가 홀수라면 *a %c 를 한 번 더 수행. 
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> A >> B >> C;
  cout << rec(A, B, C);
  return 0;
}
// http://boj.kr/9c320eecca4b4958bd54977f83371a36

이 함수의 시간 복잡도는 b가 계속 절반씩 깎이니까 O(log b)이다. 

그래서 문제의 시간 제한을 넉넉히 지킬 수 있다. 

0x02 연습문제2 - 하노이 탑 

두 번째 문제는 재귀 문제 중에 스테디셀러인 하노이탑 문제다. 

온라인 게임으로 원판 3, 4, 5개일 때를 깨고 오자. 하노이탑 문제가 뭔지 감이 올 것이다. 

그리고 백준 11729번 하노이 탑 이동순서 문제를 읽고 오자. 

읽고나서 드는 느낌은 '막막하다...?' 일단 n번 원판에만 집중해보자. 

어찌됬든 원판들을 전부 기둥1에서 기둥3으로 옮기려면, 

제일 아래 있는 n번 원판을 기둥1에서 기둥3으로 옮겨야 한다. 

그런데 n번 원판을 옮기려면 n-1번부터 1번까지의 원판들이 비켜줘야 하고 나아가 그것들이 기둥2에 가있어야 한다.

왜냐하면 작은 원판 위에 큰 원판을 둘 수 없다는 규칙 때문이다. 

n-1개의 원판을 기둥2로 옮긴다. 

그리고 n번 원판을 기둥3으로 옮긴다. 

이 다음에는 어떻게 해야 할까? 

n-1개의 원판을 기둥2에서 기둥3으로 옮기면 된다.

과정을 보면, n-1개의 원판을 원하는 곳으로 옮길 수 있으면 n개의 원판을 처리할 수 있다. 

구현을 위해 단계적으로 생각해보자. 

1. 함수의 정의 

func(n)함수가 func(n-1)함수를 호출하는 방법이 가능할까? 

문제 요구사항은 원판 n개를 기둥a에서 기둥b로 옮기는 방법을 출력하는 것이다. 따라서 func(n-1)은 이 문제에 부적절하다. 

따라서 아래처럼 정의하자. 

void func(int a, int b, int n)

2. base condition

재귀가 자기자신을 호출하지 않고 종료하는 조건을 정의하자. 

원판 1개인 경우를 생각해보자. 

n=1 일 때, a에서 b로 옮기도록 하면 된다. 

n=1 일 때, cout << a << ' ' << b <<'\n';

3. 재귀 식 

기둥 a에서 기둥 6-a-b로 옮긴다. 

이건 바로 이해가 안 갈 수 있다. 기둥 번호 1, 2, 3번의 합이 6이라는 것을 생각하면서 아래의 재귀식을 읽어보자. 

방금 봤던 이동순서 그림을 다시 보고 오면 도움이 된다. 

n번 원판을 기둥 a에서 기둥 b로 옮긴다.                   --> n번 원판을 기둥 1에서 기둥 2로 옮긴다. 
n-1개의 원판을 기둥 a에서 기둥 6-a-b로 옮긴다.  --> n-1개의 원판을 기둥 1에서 기둥 3으로 옮긴다. 

기둥1을 기둥a라는 공통의 출발지로 본다면, 

n-1개의 원판은 6-a-b로 옮겨야 하고, n번 원판은 b로 옮겨야 한다. 

n-1개의 원판을 기둥a에서 기둥 6-a-b로 옮긴다.  func(a, 6-a-b, n-1);
n번 원판을 기둥 a에서 기둥b 로 옮긴다. 		cout << a << ' '<< b << '\n';
n-1개의 원판을 기둥 6-a-b에서 기둥b로 옮긴다.  func(6-a-b, b, n-1);

4. 원반을 옮긴 횟수 

원반 k개를 옮기기 위해 A번 이동이 필요하다고 하자. 

그러면 원반 k+1개를 옮길 때는 몇 번이 필요할까? 

k개의 원판을 빈 곳으로 옮길 때 A번, (이미 알고 있다)
k+1번 원판을 옮길 때 1번,
k개 원판을 다시 빈 곳에서 목적지로 옮길 때 A번이 필요하다. 
->   즉, 2A+1번 이동이 필요하다. 

구현 코드

//바킹독님코드 http://boj.kr/f2440915dca04aaa9aec759080516973
#include <bits/stdc++.h>
using namespace std;

void func(int a, int b, int n){
  if(n == 1){
    cout << a << ' ' << b << '\n';
    return;
  }
  func(a, 6-a-b, n-1);
  cout << a << ' ' << b << '\n';
  func(6-a-b, b, n-1);
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int k;
  cin >> k;
  cout << (1<<k) - 1 << '\n';  // (1<<k)는 2의 k승이다. 
  func(1, 3, k);
}

0x03 연습문제3 - Z

하노이탑이 아리송하지만. 백준 1074번 Z문제를 읽어 보면 '또 뭔가..' 싶을 것이다.

꾹 참고 5분만 재귀 관점으로 고민해보자. 

방문 순서가 어떤 식으로 매겨지냐면, 배열을 4등분 한 후에, 1,2,3,4 순으로 진행된다. 

아래 그림에서 N=3일 때, 16x16 배열을 그려놓고. 4등분 해서 영역 1,2,3,4로 나눠놨다. 

r=2, c=2 칸은 '영역1'에서' 12번째로 방문한다. 

'영역1' 내부를 4등분으로 나누면, 영역 1, 2, 3에 포함된 0칸~11칸을 전부 방문하고, 12번째로 방문한 셈이다. 

r=6, c=2칸은 '영역3'에서 44번째로 방문한다. 

'영역3'에 오기 전에는 이미 '영역1, 영역2'를 방문한다. '영역3'내부의 0칸~11칸을 전부 방문하고, 12번째로 방문한 셈이다. 

뭔가 이전에 방문한 순서를 기반으로 다음 것을 구할 때 써먹을 수 있을 것 같다는 느낌이 조금 온다. (그저 느낌뿐..)

구현을 위해 단계적으로 생각해보자. 

1. 함수의 정의 

직관적으로 보이는 모양 대로 정의하면 된다. 2의 N승 배열에서, (r,c)를 방문하는 순서를 반환하는 함수. 

이 값이 Int범위에 들어오는지 신경써줄 필요가 있는데, n은 15이하니까 int범위를 초과하지 않는다. 

int func(int n, int r, int c)

2. base condition

n=0일 때 0을 반환하도록 하자. 

n=0 일 때, return 0;

3. 재귀 식 

각 상황에 따른 반환 값은 아래와 같다. 

여기서 half는 한 변 길이의 절반, 즉 2의 n-1승이다. 

(r,c)가 1번 영역일 때, return func(n-1, r, c);
(r,c)가 2번 영역일 때, return half*half    + func(n-1, r, c-half);
(r,c)가 3번 영역일 때, return 2* half*half + func(n-1, r-half, c);
(r,c)가 4번 영역일 때, return 3* half*half + func(n-1, r-half, c-half);

아까 그림을 보며 확인한 12번째 방문한다는 것의 의미를 다시 보자.

12번째 방문한다는 것은 0칸~11칸을 전부 방문하고, 12번째로 방문하는 것이다.

2의 2승 을 4등분한 영역에서, 2의 1승(2의 n-1승) 영역의 1,2,3영역을 모두 방문한 다음에 4영역을 방문하고 있는 것이다. 

풀이 코드 

// http://boj.kr/fd805e1226e949f9b6b2eff59e5be642
#include <bits/stdc++.h>
using namespace std;

int func(int n, int r, int c){
  if(n == 0) return 0;
  int half = 1<<(n-1);
  if(r < half && c < half) return func(n-1, r, c);
  if(r < half && c >= half) return half*half + func(n-1, r, c-half);
  if(r >= half && c < half) return 2*half*half + func(n-1, r-half, c);
  return 3*half*half + func(n-1, r-half, c-half);
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, r, c;
  cin >> n >> r >> c;
  cout << func(n, r, c);
}

재귀 문제집

다음 시간에 배울 백트래킹을 잘 해내기 위해서라도 재귀를 능숙하게 다룰 수 있도록 연습을 많이 하자. 반복 또 반복.

문제집에 있는 문제들이 쉽지는 않겠지만,

풀이를 보고 푸는 한이 있더라도 재귀가 두렵지 않을 때 까지 연습을 한 후에 백트래킹으로 넘어가자. 

다음 시간에는 백트래킹을 공부한다.

공부 자료 출처 : 바킹독 알고리즘 재귀 

문제

수 찾기 백준 1920

"맞았습니다"코드

#include <bits/stdc++.h>
using namespace std;

int n, m, num;
int arr[100010];

void binarySearch(int target){
  int start = 0;
  int end = n-1;
  int mid = 0;

  while(end >= start){
    mid = (start+end)/2;

    if(target == arr[mid]){
      cout << 1 << '\n';
      return;
    }
    else if (arr[mid] < target){
      start = mid+1;
    }
    else{
      end = mid-1;
    }
  }
  cout << 0 << '\n';
  return;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> arr[i];
  }
  sort(arr, arr+n); // 이분탐색을 위해 미리 정렬 
  cin >> m; 
  while(m--){
    cin >> num;
    binarySearch(num);
  }
  return 0;
}

리뷰

이중 for문으로 검사하면 n, m둘다 10만개가 주어질 수 있기 때문에.
시간초과가 난다.
따라서 첫 번째 배열을 정렬 시키고, 두 번째 숫자가 들어올 때마다 이분 탐색시켰다.

문제

상범빌딩 백준 6593

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int L, R, C; // 층, 행, 열
int bd[35][35][35];
int vis[35][35][35]; // 거리 저장 
int dx[] = {0, 0, 0, 0, 1, -1}; // 층
int dy[] = {0, 1, 0, -1, 0, 0}; // 행 
int dz[] = {1, 0, -1, 0, 0, 0}; // 열 
queue<pair<pair<int,int>, int>> qu; // 층, 행, 열
int exittime; // 탈출시간

bool rangecheck(int i, int j, int k){ // 층, 행, 열 유효범위 검사
  return (i >=0 && i < L && j >= 0 && j < R && k >=0 && k < C);
}

void initvis(){ // 방문배열 초기화
  for(int i = 0; i < 35; i++)
    for(int j = 0; j < 35; j++) {
      fill(vis[i][j], vis[i][j] + 35, -1);
      fill(bd[i][j], bd[i][j] + 35, 0);
    }
}

int bfs(){
  while(!qu.empty()) {
    int curx = qu.front().X.X;
    int cury = qu.front().X.Y;
    int curz = qu.front().Y;
    qu.pop();

    if(bd[curx][cury][curz] == 3) return vis[curx][cury][curz];

    for (int i = 0; i < 6; i++) {
      int nx = dx[i] + curx;
      int ny = dy[i] + cury;
      int nz = dz[i] + curz;

      // 벽(1)이면 못감. 유효범위, 방문여부 확인
      if (!rangecheck(nx, ny, nz) || bd[nx][ny][nz] == 1 || vis[nx][ny][nz] >= 0) continue;
      vis[nx][ny][nz] = 1+vis[curx][cury][curz]; // 방문
      qu.push({{nx,ny},nz});
    }
  }
  return -1;
}


void input(){ // 입력받기

  // 초기화
  initvis();
  while(!qu.empty()) qu.pop(); // 큐 비우기

  // 입력받기
  char ch;
  for(int i = 0; i < L; i++) { // 층
    for (int j = 0; j < R; j++) { // 행
      for (int k = 0; k < C; k++) { // 열
        cin >> ch;
        if (ch == '#') { // 벽 1
          bd[i][j][k] = 1;
        } else if (ch == 'S') { // 시작 위치 2
          bd[i][j][k] = 2;
          vis[i][j][k] = 0;
          qu.push({{i,j},k});
        } else if (ch == 'E') { // 출구 3
          bd[i][j][k] = 3;
        }
      }
    }
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  while(1){
    cin >> L >> R >> C; // 입력받기
    if(L==0 && R ==0 && C==0) break; // 종료조건
    input();
    int result = bfs();
    if(result < 0) cout << "Trapped!" << '\n';
    else  cout << "Escaped in "<<result << " minute(s)." << '\n';
  }
  return 0;
}

리뷰

문제를 주의 깊게 안읽어서 고생했다.

3차원 토마토 문제랑 거의 똑같다. 시작 위치와 탈출 위치가 정해져 있다.

vis 배열은 거리를 저장하고 방문여부를 구분하기 위해 -1로 초기화했다.

bd 배열은 1이면 벽으로 표시해서 방문하지 못하게 했다.

vis 배열에는 거리를 저장했다. 그래서 시작 위치에서는 0이다.

테스트케이스가 여러개니까 방문배열과 큐를 반드시 초기화한 다음에 bfs를 돌아야 한다.

큐에 '거리'(==이동 횟수) 를 저장하는 방법으로도 풀었다.

코드링크

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int L, R, C; // 층, 행, 열
int bd[35][35][35];
bool vis[35][35][35];
int dx[] = {0, 0, 0, 0, 1, -1}; // 층
int dy[] = {0, 1, 0, -1, 0, 0};
int dz[] = {1, 0, -1, 0, 0, 0};
queue<pair<pair<int,int>, pair<int,int>>> qu; // 층, 행, 열, 이동횟수

bool rangecheck(int i, int j, int k){ // 층, 행, 열 유효범위 검사
  return (i >=0 && i < L && j >= 0 && j < R && k >=0 && k < C);
}

void initvis(){ // 방문배열 초기화
  for(int i = 0; i < 35; i++)
    for(int j = 0; j < 35; j++) {
      fill(vis[i][j], vis[i][j] + 35, false);
      fill(bd[i][j], bd[i][j] + 35, 0);
    }
}

int bfs(){

  while(!qu.empty()) {
    int curx = qu.front().X.X;
    int cury = qu.front().X.Y;
    int curz = qu.front().Y.X;
    int curcnt = qu.front().Y.Y;
    qu.pop();

    if(bd[curx][cury][curz] == 3) return curcnt;

    for (int i = 0; i < 6; i++) {
      int nx = dx[i] + curx;
      int ny = dy[i] + cury;
      int nz = dz[i] + curz;

      // 벽(1)이면 못감. 유효범위, 방문여부 확인
      if (!rangecheck(nx, ny, nz) || bd[nx][ny][nz] == 1 || vis[nx][ny][nz]) continue;
      vis[nx][ny][nz] = true; // 방문
      qu.push({{nx,ny},{nz, curcnt+1}});
    }
  }
  return -1;
}


void input(){ // 입력받기

  // 초기화
  initvis();
  while(!qu.empty()) qu.pop(); // 큐 비우기

  // 입력받기
  char ch;
  for(int i = 0; i < L; i++) { // 층
    for (int j = 0; j < R; j++) { // 행
      for (int k = 0; k < C; k++) { // 열
        cin >> ch;
        if (ch == '#') { // 벽 1
          bd[i][j][k] = 1;
        } else if (ch == 'S') { // 시작 위치 2
          bd[i][j][k] = 2;
          vis[i][j][k] = true;
          qu.push({{i,j},{k,0}});
        } else if (ch == 'E') { // 출구 3
          bd[i][j][k] = 3;
        }
      }
    }
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  while(1){
    cin >> L >> R >> C; // 입력받기
    if(L==0 && R ==0 && C==0) break; // 종료조건
    input();
    int result = bfs();
    if(result < 0) cout << "Trapped!" << '\n';
    else  cout << "Escaped in "<<result << " minute(s)." << '\n';
  }
  return 0;
}

목차

0x00 DFS 알고리즘 설명 

0x01 예시 

0x02 BFS vs DFS 

0x00  DFS 알고리즘 

DFS (Depth First Search)

다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 

BFS (Breadth First Search)

다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

0x01 DFS 예시

BFS에서는 queue를 사용해서 모든 칸을 검사했었다. 

DFS는 큐 대신 stack 을 쓰는 것 뿐이고 나머지는 BFS와 똑같다. 

(0,0)에서 시작하여 상하좌우로 인접한 같은 색의 칸을 방문하는 Flood Fill을 구현해보자. 

아래는 좌표 배열이 있고, DFS를 위한 stack이 있다. 

탐색 흐름을 그림으로 확인하자. 

1. (0,0)시작점에 방문표시를 하고, stack에 push한다. 

스택이 빌 때까지 계속 스택의 top을 확인하여 상하좌우를 살펴보며 미방문한 좌표를 스택에 푸시하는 작업을 반복한다. 

2. 현재 스택의 top은 (0,0)이다.

(0,0)을 pop()해서 (0,0)의 상하좌우를 확인한다. 

파란 칸이면서 방문하지 않은 좌표를 스택에 push한다. -> (1,0)과 (0,1)을 push

3. 현재 스택의 top은 (1,0)이다.

(1,0)을 pop() 해서 (1,0)의 상하좌우를 확인한다. 

(0,0)은 이미 방문했고, (1,1)은 못간다. (2,0)은 방문하지 않은 칸이다. 

(2,0)에 방문표시를 하고 stack에 push한다. 

4. 이제 스택의 top은 (2,0)이 된다. (2,0)을 pop한다. 

전체 과정 그림으로 보기

0x02 BFS vs DFS 

BFS는 queue를 쓰고 DFS는 stack을 쓴다는 차이가 있지만, 원소 하나를 빼내서 주변을 살핀다는 알고리즘의 흐름은 똑같다. 

이 그림에서 관찰할 점은 방문순서다.

BFS

중앙의 1번 칸을 중심으로 주위를 보면, 1방문 후에 상하좌우 2,3,4,5번 방문한다.

마치 냇가에 던진 돌로 인해 동심원이 생기는 것처럼 상하좌우로 퍼져나간다. 

이전 강의에서 배운 '거리 순으로 방문한다'는 성질을 확인할 수 있다. 

DFS

갈 수 있을 때 까지 간다.

가능한 깊게 직진하는 모양이다. depth 우선 탐색이라는 성질을 그림으로 확인할 수 있다. 

거리 잴 때 DFS? BFS?

Flood Fill을 구현할 때 DFS, BFS 무엇을 쓰든 상관은 없다.

하지만 BFS에서 거리 잴 때 유용하게 썼던 "현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재보다 1만큼 떨어져있다"는 성질이 DFS에서는 성립하지 않는다. 

결국 다차원 배열에서 굳이 DFS를 쓸 일이 없다. 거리측정은 BFS만 가능하기 때문이다. 

DFS는 그래프와 트리라는 자료구조를 쓸 때 짜게 된다. 

이 수업에서는 DFS는 stack을 써서 다차원배열을 순회하는 알고리즘 이라고만 기억하고 넘어가자. 

다음 시간에는 재귀를 공부한다. 

공부 자료 출처 : 바킹독 알고리즘 DFS

목차

0x00 BFS 알고리즘 설명 

0x01 예시 

0x02 응용1 - 거리 측정 

0x03 응용2 - 시작점이 여러 개일 때 

0x04 응용3 - 시작점이 두 종류일 때 

0x05 응용4 - 1차원에서의 BFS 

0x00 BFS 알고리즘 

Breadth-First Search 너비 우선 탐색.

다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문한다. 

하나의 노드를 기준으로, 

깊이가 1인 모든 노드를 방문한다.

깊이가 2인 모든 노드를 방문한다. 

깊이가 3인 모든 노드를 방문한다. 

빠짐 없이 모든 노드를 방문하면, 탐색을 마친다. (예시 그림에서 다시 이해해보자)

특징 

재귀적으로 동작하지 않는다. (반면, DFS는 재귀적으로 동작한다)

노드의 방문 여부를 반드시 검사한다. 이를 검사하지 않으면 무한 루프에 빠진다. 

0x01 BFS 예시 

목표: (0,0)과 상하좌우로 인접한 모든 파랑 칸을 확인하여 개수를 세자. 

BFS알고리즘에서는 좌표를 담을 큐가 필요하다. 그래서 좌표 옆에 있는 작대기는 큐를 표현한 것이다. 

1. (0,0)에 방문했다는 표시(검정색 점)를 남기고, 큐에 (0,0)를 넣는다.  

이 초기 세팅이 끝난 후에는, 큐가 빌 때까지 계속 큐의 front()를 pop()한다. 

front()에서 pop()한 좌표의 상하좌우를 살펴보면서 큐에 넣어주는 작업을 반복하게 된다. 

2. 큐에서 뺀 (0,0)의 상하좌우를 확인한다.

그림에서 현재 위치한 칸은 빨강테두리고, 상하좌우 확인하고 있는 칸은 검정 테두리다. 

상하좌우 중에서 (0,1) 과 (1,0)이 유효한 좌표이다. 

파랑색 칸이면서 아직 방문하지 않은 칸(검정 점 표시가 없는 칸)을 큐에 넣자. 

-> (0,1) 과 (1,0) 을 큐에 넣는다. 이제 큐에는 좌표가 2개 쌓였다. 

3. 다음으로 넘어간다. 큐의 front()는 (0,1)이다.

(0,1)을 pop()뺀다.  참고로 (0,1)에서 (행,열)순이다. 

(0,1)의 상하좌우를 확인하여 방문하지 않고, 파란칸인 것을 큐에 push한다. 

(0,2)는 파란칸이면서 방문하지 않은 칸이니까 방문표시를 남기고 큐에 넣는다. 

전체 과정은 여기를 참고하자. 

4. 큐가 빈 순간,탐색이 종료된다. 아래는 BFS 과정을 정리한 것이다. 

BFS의 시간 복잡도 

방문 표시를 남기기 때문에 모든 칸은 큐에 1번씩 들어간다. 

그러므로 시간 복잡도는 칸이 N개일 때 O(N)이 된다. 만약 행이 R개이고 열이 C개이면 O(RC)가 된다. 

STL pair : 좌표 저장에 유용함

큐에 좌표를 넣을 때 pair로 저장하면 유용하다. 

레퍼런스 링크 

방향 배열

상하 좌우를 탐색할 때, 아래의 방향 배열 dx, dy를 정의해두고 사용하면 편리하다. 

만약 3차원이 주어지고 위, 아래를 검사해야한다면, 여기에 dz를 추가하여 x,y,z를 더하고 빼면 된다. 

int dx = {0, 1, 0, -1};
int dy = {1, 0, -1, 0};

코드의 depth 깊게 하지 않기

유효좌표 검사 등 여러 조건 확인 시 continue를 써서 코드의 depth를 덜 깊어지게 하자. 가독성을 위함. 

BFS 기본 코드

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
int board[502][502] =
{{1,1,1,0,1,0,0,0,0,0},
 {1,0,0,0,1,0,0,0,0,0},
 {1,1,1,0,1,0,0,0,0,0},
 {1,1,0,0,1,0,0,0,0,0},
 {0,1,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0} }; // 1이 파란 칸, 0이 빨간 칸에 대응
bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장
int n = 7, m = 10; // n = 행의 수, m = 열의 수
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; // 상하좌우 네 방향을 의미
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  queue<pair<int,int> > Q;
  vis[0][0] = 1; // (0, 0)을 방문했다고 명시
  Q.push({0,0}); // 큐에 시작점인 (0, 0)을 삽입.
  while(!Q.empty()){
    pair<int,int> cur = Q.front(); Q.pop();
    cout << '(' << cur.X << ", " << cur.Y << ") -> ";
    for(int dir = 0; dir < 4; dir++){ // 상하좌우 칸을 살펴볼 것이다.
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 밖일 경우 넘어감
      if(vis[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우
      vis[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
      Q.push({nx,ny});
    }
  }
}

[중요] BFS 구현 시 자주 하는 실수

1. 시작점에 방문했다는 표시를 남기지 않는다. 
방문 배열에 꼭 방문 표시를 남겨야 재방문 하지 않고 무한루프로 빠지지 않는다. 

2. 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문 했다는 표시를 남겼다.
같은 칸이 큐에 여러번 들어가서 시간초과나 메모리 초과가 날 수 있다. 

3. 이웃한 원소가 유효범위를 벗어났는지에 대한 체크를 잘못했다. 
배열 인덱스가 음수가 되거나 유효범위를 넘어가면 런타임 에러가 난다. 

0x01 예시 문제 : 기본 BFS 

BFS 기본 예제를 풀어본다.  백준 1926번 그림

해결 과정 

1. 이중 for문으로 그림이 시작되는 칸에서 BFS를 시작한다.

2. 그림이 연결된 칸이 몇개인지 알려면? 큐에서 pop을 몇 번 하는지 센다. 그림 칸이지만, 이미 방문한 칸이라면 BFS를 시작할 수 없다. 

결국 파란 칸은 큐에 딱 한번씩만 들어가니까 시간 복잡도는 칸의 갯수만큼 O(nm)이다. 

0x02 응용1 - 거리 측정

백준 2178번 미로탐색

미로 좌측 상단으로부터 우측 하단으로 가는 최단 경로의 길이를 찾는 문제다. 

BFS를 이용해 시작점에서 연결된 다른 모든점으로의 최단 경로를 찾을 수 있다. 

이번에는 방문했다는 표시 대신에, 각 칸들에 (0,0)까지의 거리를 저장한다. 

미로를 저장하는 배열을 미로 -1로 초기화해두면 굳이 방문배열을 두지 않아도 방문여부를 확인할 수 있다. 

// http://boj.kr/cd14bec9ecff461ab840f853ed0eb87f
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[102];
int dist[102][102];
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for(int i = 0; i < n; i++)
    cin >> board[i];
  for(int i = 0; i < n; i++) fill(dist[i],dist[i]+m,-1);  // -1로 초기화한다 
  queue<pair<int,int> > Q;
  Q.push({0,0});
  dist[0][0] = 0;
  while(!Q.empty()){
    auto cur = Q.front(); Q.pop();
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 유효범위 확인 
      if(dist[nx][ny] >= 0 || board[nx][ny] != '1') continue; // 이미 방문했는지. 벽이 아닌지.
      dist[nx][ny] = dist[cur.X][cur.Y]+1;
      Q.push({nx,ny});
    }
  }
  cout << dist[n-1][m-1]+1; // 문제의 특성상 거리+1이 정답
} // 바킹독님 코드

0x03 응용2 - 시작점이 여러 개일 때 

백준 7576번 토마토

토마토가 익어가는 것이 익은 것을 중심으로 상하좌우로 퍼져간다. 

토마토가 다 익기까지 필요한 최소 일 수를 구하려면? 

-> 모든 익지 않은 토마토들에 대해 가장 가깝게 위치한 익은 토마토까지의 거리를 구해야한다. 익지 않은 토마토가 있다면 -1 출력.

BFS의 시작점은 '익은 토마토'다. (초록칸)
따라서 BFS의 시작점은 여러개의 익은 토마토 좌표들이다.  

모든 익은 토마토의 좌표를 큐에 전부 넣는다. 

그리고 BFS를 시작한다. 

코드를 보며 이해해보자. 

// http://boj.kr/ae38aa7eb7a44aca87e9d7928402d040 
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[1002][1002];
int dist[1002][1002];
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> m >> n;
  queue<pair<int,int> > Q;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cin >> board[i][j];
      if(board[i][j] == 1) // 익은 토마토는 시작점이니까 큐에 넣는다. 
        Q.push({i,j});
      if(board[i][j] == 0) // 아직 안익은 토마토는 -1 로 표시한다. 
        dist[i][j] = -1;
    }
  }
  while(!Q.empty()){
    auto cur = Q.front(); Q.pop();
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 유효한 범위인지? 
      if(dist[nx][ny] >= 0) continue; // 이미 방문.
      dist[nx][ny] = dist[cur.X][cur.Y]+1;
      Q.push({nx,ny});
    }
  }
  int ans = 0;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(dist[i][j] == -1){ // 아직 익지않은 토마토가 있으면? 실패. 
        cout << -1;
        return 0;
      }
      ans = max(ans, dist[i][j]); // 가장 먼 거리.
    }
  }
  cout << ans;
}

해결 과정 

1. 입력 받으면서 익은토마토만 큐에 넣는다. 

2. 익지 않은 토마토는 dist 배열값을 -1로 둔다. 토마토가 없는 빈칸은 dist 배열 값이 0이다. 

3. BFS를 돌면서 -1인 칸(아직 익지 않은 토마토)의 거리를 갱신해준다. 

4. 마지막에서, 거리가 가장 먼 것을 찾는다. 

참고) 큐에 쌓이는 거리 

1. 처음 입력을 받을 때, 익은 토마토들은 거리가 0이다. (시작점은 거리가0) 

2. 시작점 주변에서 익혀진 토마토는 거리가 1이 된다. 

3. 1인 칸들을 pop하는 동안 거리가 2인 칸들이 push된다. 

4. 거리가 2인 칸들을 검사하는 동안 거리가 3인 칸들이 push된다. 

즉, 전체적인 큐의 모양을 보면 '큐에 쌓이는 순서는 반드시 거리 순'이게 된다. 

이 문제는 2차원  토마토였고, 3차원 토마토 문제도 풀어보자. 

0x04 응용3 - 시작점이 두 종류일 때

백준 4179번 불!

불과 지훈이가 동시에 움직인다. 문제를 읽어보면 막막할 수 있지만 지금 배운 BFS응용이니까 고민해보자. 

지훈이가 이동하다가 미로 맨 가장자리에 도착하면 탈출시켜야 한다. 

결론부터 말하면, 불의 BFS와 지훈이의 BFS를 모두 돌림으로써 해결할 수 있다. 

파랑칸은 지훈이 위치고, 빨강칸은 불의 위치다. 

해결 과정 

1. 먼저 지훈이는 신경쓰지 말고, 불의 BFS를 돌려서 미리 각 칸에 불이 전파되는 시간을 구해둔다. 

불 시간을 저장할 배열을 사용한다. 

위 그림에서 '두 번째 맵'이 각 칸에 불이 전파 시간을 의미한다. 

2. 그 다음에 지훈이에 대한 BFS를 돌려서 지훈이를 이동시킨다. 

지훈이 이동시간을 저장할 배열을 사용한다. 

이 때, 만약 지훈이가 특정 칸을 x시간에 최초로 방문할 수 있는데, 그 칸에 x시간이나 그 이전에 불이 붙는다면? 그 칸에 못가게 된다. 

3. 여태 까지 BFS를 풀 때의 방문 여부 방법은?

큐 안에서 (nx, ny)를 검사할 때 방문여부를 vis[nx][ny]가 true인지 혹은 dist[nx][ny]가 0이상인지 확인했었다. 

이 문제에서는 추가로 해당 칸에 불이 붙는 시간을 확인해야 한다. 

바킹독님 불! 코드 

// http://boj.kr/aed4ec552d844acd8853111179d5775d
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[1002];
int dist1[1002][1002]; // 불의 전파 시간
int dist2[1002][1002]; // 지훈이의 이동 시간
int n, m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for(int i = 0; i < n; i++){ // 모든 방문배열 -1로 초기화 하여 미방문 표시하기 
    fill(dist1[i], dist1[i]+m, -1);
    fill(dist2[i], dist2[i]+m, -1);    
  }
  for(int i = 0; i < n; i++)
    cin >> board[i];  
  queue<pair<int,int> > Q1;
  queue<pair<int,int> > Q2;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(board[i][j] == 'F'){ // 불이면 큐1에 푸시. 거리도 배열1에 0초기화.
        Q1.push({i,j});
        dist1[i][j] = 0;        
      }
      if(board[i][j] == 'J'){ // 지훈이 시작점은 큐2에 푸시. 거리도 배열2에 0초기화.
        Q2.push({i,j});
        dist2[i][j] = 0;
      }
    }
  }
  // 불에 대한 BFS
  while(!Q1.empty()){
    auto cur = Q1.front(); Q1.pop();
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; 
      if(dist1[nx][ny] >= 0 || board[nx][ny] == '#') continue; // 벽이거나 이미 방문했으면 지나감
      dist1[nx][ny] = dist1[cur.X][cur.Y]+1;
      Q1.push({nx,ny});
    }
  }

  // 지훈이에 대한 BFS
  while(!Q2.empty()){
    auto cur = Q2.front(); Q2.pop();
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m){ // 범위를 벗어났다는 것은 탈출에 성공했다는 의미. 큐에 거리 순으로 들어가므로 최초에 탈출한 시간을 출력하면 됨.
        cout << dist2[cur.X][cur.Y]+1; 
        return 0;
      }
      if(dist2[nx][ny] >= 0 || board[nx][ny] == '#') continue;
      if(dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y]+1) continue; // 불의 전파 시간을 조건에 추가
      dist2[nx][ny] = dist2[cur.X][cur.Y]+1;
      Q2.push({nx,ny});
    }
  }
  cout << "IMPOSSIBLE"; // 여기에 도달했다는 것은 탈출에 실패했음을 의미.
}

0x05 응용4 - 1차원에서의 BFS 

백준 1697번 숨바꼭질

지금까지는 2차원 배열에서 상하좌우를 검사했었다. 

문제에서 수빈이가 이동하는 것을 보면, 현재 위치 x를 기준으로 x+1, x-1, x*2 의 위치로 이동할 수 있다. 

해결 과정 

1. 시작점이 5라면, BFS의 시작점을 5로 잡고 큐에 push()한다. 

2. 큐의 front()는 5다.

5에서 갈 수 있는 거리는 4, 6, 10이 되고 5에서 부터의 거리는 1이 된다. 

따라서 4, 6, 10에 1을 저장한다. 

3. 위치 4, 6, 10을 큐에 push() 한다. 

4. 큐의 front()는 4다. 

위치 4에서는 3, 5, 8에 갈 수 있다. 거리를 +1해서 거리2를 3,5,8에 저장한다. 

5. 이렇게 BFS를 진행 하다가 동생이 있는 위치를 만나면 거리를 출력한다. 

주의

-> 0부터 10만의 제한이 있다. 거리 이동범위가 *2가 제일크다. 아무리 멀리 가도 20만이 된다. 

바킹독님 숨바꼭질 코드

BFS 문제집

BFS부터는 코딩테스트에 정말 잘나오는 유형이기 때문에 문제집을 꼼꼼하게 풀고, 코드의 흐름을 익히자. 

다음 시간에는 DFS를 배운다. 

그림 및 공부 자료 출처 : 바킹독 알고리즘 - BFS

문제

나무 자르기 백준 2805

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

// 2805 나무자르기
long long n, m, num, answer;
vector<long long> v;

void bs(){

  int start = 0;
  int end = *max_element(v.begin(), v.end());
  int mid = 0;

  while(start <= end){
    mid = (start+end)/2;

    long long tempsum = 0;
    for(int i=0; i <n; i++){
      if(v[i]>mid) tempsum += (v[i]-mid);
    }
    if(tempsum >= m){  // 조건 만족시, 
      answer = mid;
      start = mid+1;
    }else{ // 덜 깎아야 함.
      end = mid-1;
    }
  }

  cout << answer;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;

  for(int i = 0; i < n; i++){
    cin >> num;
    v.push_back(num);
  }

  bs();
  return 0;
}

리뷰

나무의 수와 높이가 꽤 크다.
나무는 백만개가 최대.
높이는 10억이 최대.

단순하게 절단기 높이를 0부터 10억까지 반복문으로 검사하기에는 시간이 오래걸린다.
10억 x 100만 이기 때문이다.

따라서 이분탐색으로 절단기의 높이를 찾는다.
이 때, 최소값은 0, 최대값은 나무중에서 제일 긴것을 기준점으로 잡는다.

이분 탐색의 중간값mid로 나무를 절단했을 때,
잘라낸 나무 누적 합(tempsum)이 기준값(m)을 만족시키면 답으로 저장해둔다.
answer = mid;

기준값보다 잘라낸게 더 많으면, 덜 깎아야 하니깐 start = mid+1; 절단기의 높이를 높여야 덜 깎는다.
기준값보다 누적합이 작으면, 더 깎아야 하니까 end=mid-1; 절단기의 높이를 줄여야 더 많이 깎여나간다.

"절단기의 높이를 줄이면, 나무가 더 많이 깎여나가니까 tempsum이 증가한다"
처음에는 이 부분이 헷갈렸었다.

문제

토마토 7569번

"맞았습니다" 코드

#include <bits/stdc++.h>
using namespace std;

// 7569 토마토
int n, m, h; // 행, 열, 높이,
int target; // 익혀야할 개수
int box[102][102][102];
int vis[102][102][102];

int dx[] = {0, 0, 0, 0, -1, 1};  // 높이
int dy[] = {0, 1, 0, -1, 0, 0}; // 행
int dz[] = {-1, 0, 1, 0, 0, 0}; // 열
queue<tuple<int, int, int>> qu; //  {h좌표, x좌표, y좌표}

void initarr(){
  for(int i = 0; i < 102; i++) { // 높이
    for (int j = 0; j < 102; j++) { // 행
      fill(vis[i][j], vis[i][j]+102, -1);
    }
  }
}
bool checkrange(int i, int j, int k){ // 높이, 행, 열 -> 유효범위 체크
  return (i > 0 && i <= h && j > 0 && j <= n && k > 0 && k <= m);
}

int bfs(){

  int day = 0;

  while(!qu.empty()){
    int curx = get<0>(qu.front()); // 높이
    int cury = get<1>(qu.front()); // 행
    int curz = get<2>(qu.front()); // 열
    qu.pop();

    for(int i = 0; i < 6; i++){ // 6방향 체크한다
      int nx = curx + dx[i];
      int ny = cury + dy[i];
      int nz = curz + dz[i];

      // 유효범위, 안익은 토마토(방문배열-1)인지, 토마토가 있는지 여부.
      if(!checkrange(nx, ny, nz) || vis[nx][ny][nz] != -1 || box[nx][ny][nz] == -1) continue;

      vis[nx][ny][nz] = vis[curx][cury][curz] + 1; // 현재날짜 +1
      day = max(day, vis[nx][ny][nz]);
      qu.push(make_tuple(nx,ny,nz));
      target--; // 익혔다

    }
  }
  return day;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> m >> n >> h; // 열,행,높이 순서 

  initarr(); // 방문배열에는 익은 날짜를 저장할 것이므로 전부 -1로 초기화

  for(int i = 1; i <= h; i++){ // 높이
    for(int j = 1; j <= n; j++){ // 행
      for(int k = 1; k <= m; k++){ // 열
        cin >> box[i][j][k];
        if(box[i][j][k] == 0) {
          target++; // 익혀야 할 토마토(0) 개수 세기
          vis[i][j][k] = -1; // 방문 타겟
        }
        if(box[i][j][k] == 1) { // 이미 익은 토마토(1) 는 시작점이 된다.
          vis[i][j][k] = 1;
          qu.push(make_tuple(i, j, k));
        }
      }
    }
  }

  if(target == 0) cout << 0; // 익혀야할 것이 없다
  else{
    int day = bfs();
    if(target == 0) cout << day-1;
    else cout << -1;
  }
  return 0;
}

리뷰

7576 토마토는 2차원이었는데, 7569 토마토는 3차원이다.
익은 토마토는 동서남북을 익히니까 익은 토마토 좌표를 모두 큐에 넣는다.
dx, dy, dz를 이용해 상하좌우 위아래 모두 확인한다.