[바킹독 BFS] 예제 다시 풀어보기 (진행 중)

바킹독님 BFS 예제 다시 풀어보기

 

BFS 기본 코드

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[502][502]={...};
bool vis[502][502];
int n=7, m=10; // 7행 10열
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}); // 시작점을 넣어준다.
    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];
        if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
        if(vis[nx][ny] || board[nx][ny]!=1) continue;
        vis[nx][ny]=1;
        Q.push({nx, ny});
        }
       }
      }

그림 문제부터 숨바꼭질 문제까지!

 

'미로 탐색'부터 먼저 풀고 마지막에 그림 풀어보기...

 

[미로 탐색]

배열을 붙여서 입력 받으면 어떻게 해야 하나요? string으로 입력 받는다.

string board[102];
int n, m;

int main(void) {
cin>>n>>m;

for(int i=0; i<n; i++)
	cin>>board[i];

 

반면 다른 문제(1926 그림)처럼 배열을 띄어쓰기로 구분해서 입력 받으려면

int n,m;
cin>>n>>m;

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>board[i][j];
        }
    }

 

-1로 n열 m행 배열을 채우기 위해서 fill은 어떻게 쓰는가.

for(int i=0; i<n; i++) fill(dist[i], dist[i]+m, -1);

 

왜 다음과 같이 갱신하는지 생각해보기

dist[nx][ny]=dist[cur.X][cur.Y]+1;

dist[nx][ny]는 dist[cur.X][cur.Y]보다 한 칸 더 옆에 있기 때문이다. 거리로 따져서 +1 되는게 당연!

 

정답 코드

#include <iostream>
#include <queue>
using namespace std;
#define X first
#define Y second

string board[102]; // 숫자가 붙여서 입력되므로 string 배열로 해준다.
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);
  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이 정답

}

그림 문제랑 기본적인 로직은 비슷한거 같다...

 

이미 생각하고 있었던 것) 문제 특성상 답은 dist배열 +1입니다.

그와 달리 토마토 문제는 거리 문제가 아니라 날짜 세리는 문제여서 배열+1 해서 답을 내는게 아님.

 

[토마토] 문제

배열 입출력 받고,

시작점이 될 수 있는지 확인하고 시작점이 될 수 있으면 Queue에 push를 해준다.

망한 코드- 예제 케이스 안 맞아서 백준에다가 질문 해둠

망한 코드 수습하니

중괄호 실수, 로직 빼먹음, 가로 세로 거꾸로 읽음 이 순서였다.

최종 코드는

#include <iostream>
#include <queue>

using namespace std;
#define X first
#define Y second

int n,m;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int board[1002][1002];
int day[1002][1002]; // 언제 방문했는지 나타냄 //bfs 돌리며 이걸로 채움.
 

int main(void){

ios::sync_with_stdio(0);
cin.tie(0);

    cin>>m>>n;
    // m이 가로, n이 세로

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>board[i][j];
        }
    }
    
    
    // m이 가로, n이 세로
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            day[i][j]=-1;
        }
    }
    queue<pair<int, int>> Q;

    // 토마토 시작점 표시
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(board[i][j]==1){
            Q.push({i,j});
            day[i][j]=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(board[nx][ny] == -1 || day[nx][ny]!=-1) continue;
            day[nx][ny]=day[cur.X][cur.Y]+1;
            Q.push({nx,ny});

        }
    }

int mx=0;
    // day에서 -1이 발견되면 -1을 출력하고 return 종료
    // 아니면 max 값 찾기
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(day[i][j]==-1 && board[i][j]!=-1){
            //정말로 없어서 -1 된 경우는 제외해준다.
                cout<<-1;
                return 0;
            }
            mx=max(mx, day[i][j]);
        }
    }
    
    cout<<mx;


}

 

[불!] 문제

58줄 dist2[cur.X][cur.Y]+1은 dist2[nx][ny] 생각하면 되는데 대입 연산하기는 그러니까...

dist2[nx][ny]에서의 시간은 dist2[cur.X][cur.Y]+1로 나타냄