JArchive 프로그래밍 일기

문제

상범빌딩 백준 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를 이용해 상하좌우 위아래 모두 확인한다.

문제

숨바꼭질3 백준 13549

"맞았습니다" 코드

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

int n, k;
int vis[100005];

bool rangecheck(int x){
  return (x >=0 && x <= 100000);
}

void bfs(){

  queue<int> qu;

  vis[n] = 0; // 수빈이의 현재 위치는 0초에 도달.
  qu.push(n);

  while(!qu.empty()){
    int cx = qu.front();
    qu.pop();

    if(cx == k){
      cout << vis[cx]<< '\n';
      break;
    }

    for(auto nx : {cx*2, cx + 1, cx - 1}){

      if(!rangecheck(nx) || vis[nx] <= (vis[cx]+1)) continue;

      if((cx*2) == nx) {
        vis[nx] = vis[cx];
      }else{
        vis[nx] = vis[cx] + 1;
      }
      qu.push(nx);
    }
  }
}

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

  int bignum = 1e9;
  fill(vis, vis+100004, bignum);

  cin >> n >> k;

  bfs();

  return 0;
}

리뷰

다시 풀어봐야 할 문제.

내가 위치 2에 있다.
위치 2에서 '위치 4'로 이동할 때, 예전에 방문할 때 보다 '적은 시간'이 걸려야 한다.
즉, '위치 4'로 가는 시간이 2초가 걸릴 수도 있고, 0초가 걸릴 수도 있다.

현재 위치2 이고, 이동 방법은 x2 해서 순간이동 하는방법, +1또는 -1하는데 1초가 걸리는 방법이 있다.
+1 을 2번 하면 2초가 걸려서 위치 4에 도착할 수 있다.
x2를 하고 순간이동하면 0초가 걸려서 위치 4에 도착할 수 있다.

따라서 위치 배열 인덱스 4에는 '0초'가 저장되어야 한다.

'가장 빠른 시간' 을 구해야 하니까 모든 위치의 초기 시간값을 2^9 로 크게 잡아놨다.

bfs로 순회할 때, "예전에 방문할 때 보다 '적은 시간'이 걸려야 한다" 를 만족시키기 위한 조건이 필요했다.

그래서 '현재시간 +1초' 와 다음위치가 저장하고 있는 도달 시간을 비교했다. 다음위치가 저장하고 있는 도달 시간이 더 커야 이동할 수 있게 했다.

현재 위치 시간이 2초 라고 했을 때. 2초 + 1초, 즉 3초가 다음 위치에 저장할 시간이 된다.
현재까지는 2초가 걸렸고 다음 위치에는 3초가 걸릴 수 있는 방법으로 현재까지 도달해왔다는 뜻이다.

다음 위치에 이미 3초가 저장되어 있다면, 다음 위치의 시간을 더 짧게 갱신해줄 필요가 없다.
다음 위치에 만약 4초가 저장되어 있다면, 3초를 저장하려고 했으니까 갱신해주면 된다.

문제

적록색약 백준 10026

"맞았습니다" 코드

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

int n, nor, abnor;
int arr[102][102];
bool vis[102][102] = {false};
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};

bool checkrange(int i, int j){
  return (i >= 0 && i < n && j >= 0 && j < n);
}

void bfs(int i, int j, int target){
  queue<pair<int,int>> qu;

  vis[i][j] = true;
  qu.push({i, j});

  while(!qu.empty()){
    int cx = qu.front().X;
    int cy = qu.front().Y;
    qu.pop();

    for(int i = 0; i < 4; i++){
      int nx = dx[i] + cx;
      int ny = dy[i] + cy;

      if(!checkrange(nx, ny) || (arr[nx][ny]!=target) || vis[nx][ny]) continue;
      vis[nx][ny] = true;
      qu.push({nx,ny});
    }
  }
}

void input(){
  cin >> n;

  string str = "";

  for(int i = 0; i < n; i++){
    cin >> str;
    for(int j = 0; j < n; j++){
      switch(str[j]){
        case 'R':
          arr[i][j] = 1; break;
        case 'G':
          arr[i][j] = 2; break;
        case 'B':
          arr[i][j] = 3; break;
      }
    }
  }
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  input();

  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(!vis[i][j]) {
        bfs(i, j, arr[i][j]);
        nor++;
      }
    }
  }

  // R -> G 으로 변경.
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(arr[i][j] == 1) arr[i][j] = 2;
    }
  }

  // 방문배열 초기화
  for(int i = 0; i < n; i++) fill(vis[i], vis[i]+n,0);

  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(!vis[i][j]) {
        bfs(i, j, arr[i][j]);
        abnor++;
      }
    }
  }

  cout << nor << ' '<< abnor;
  return 0;
}

리뷰

유기농 배추 문제와 비슷한 기본적인 bfs 문제였다.

R, G, B 문자는 숫자로 변경해서 저장했다. 나는 string을 이용해서 한 줄 받은다음에, 하나씩 int로 넣었는데.
다른분 코드를 보니 int 그대로 저장하는 방법도 있었다.

코드 순서는 아래와 같다.

1. 이중 for문을 돌면서, 방문하지 않은 칸인 경우 bfs를 시작한다. 이 때, 파라미터로 현재 칸의 색깔숫자를 넘긴다.
2. 현재 칸의 색깔 숫자와 같으면서도 미방문인 칸을 큐에 push하면서 bfs를 수행한다.
3. 이렇게 bfs를 돌리면서 vis배열이 꽉 차면 적록색약이 아닌사람이 볼 떄의 공간개수가 nor에 저장된다.
4. 적록색약인 경우 1인 칸과 2인칸이 똑같이 보이도록 1을 2로 바꿔준다. 이중 for문을 돈다.
5. 방문 배열을 초기화한다.
6. 현재 칸의 색깔 숫자와 같으면서도 미방문인 칸을 큐에 push하면서 bfs를 수행한다. 이 때 bfs를 도는 횟수가 abnor에 저장된다. ( abnor == 적록색약인 사람이 구분하는 영역의 개수)