Today I learned : BFS 3문제.. 그외 마무리 이것저것 함
오늘 할 일
ㅁㅈ님한테 카톡으로 링띤 포스트 보내주기 ㅋㅋ아침에 참조 올릴 메일 주소 받고 + 최종본 전달하고오전에 서류 작성 빨리 끝내기..!질문!!! 질문 생각해!!!!!BFS 오늘은 해야돼… 더이상 BFS에만 머무를 순 없어…퇴근하고 휘낭시에 픽업+피티 + 화과자…- 메신저 보고 적을 건 적기!
퇴근쯤에 컴퓨터 파일들 정리하기!!윈도우 컴으로 메일 제출!!!
응용1 - 거리 측정
2178번
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string tmp[101];
int board[101][101];
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);
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>tmp[i]; //string형 tmp에 다 받기
for(int i=0;i<n;i++) fill(board[i],board[i]+m,-1); //board에 다 -1로 채우기
queue<pair<int,int>> Q;
Q.push({0,0}); // 0,0부터 시작 (1,1)에서 출발하는 문제이니까
board[0][0]=1; //방문 시작 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-1||ny<0||ny>m-1) continue;
if(board[nx][ny]>0 || tmp[cur.X][cur.Y]!='1') continue; // tmp에서 1이 아니거나 board가 양수칸이거나
board[nx][ny]=board[cur.X][cur.Y]+1; //이전 칸의 누적칸 + 1칸
Q.push({nx,ny});
}
}
cout<<board[n-1][m-1];
}
응용2 - 시작점이 여러 개일 때
7576번
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[1001][1001];
int vis[1001][1001];
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);
int n,m;
queue<pair<int,int>> Q;
cin >> m >> n;
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) vis[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-1||ny<0||ny>m-1) continue;
if(vis[nx][ny]>=0) continue;
vis[nx][ny]=vis[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(vis[i][j]==-1){
cout<<-1;
return 0;
}
ans=max(ans,vis[i][j]);
}
}
cout<<ans;
}
시작점이 여러개일 때는 그냥 while문 돌리기 전에 큐에 시작점들을 다 넣고 시작하면 된다!
응용3 - 시작점이 두 종류일 때
4179번인데 한 번 고민을 해보래서 좀 그려지는 게 있나 확인해보자.
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[1002];
int dis1[1002][1002];
int dis2[1002][1002];
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);
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
fill(dis1[i],dis1[i]+m,-1);
fill(dis2[i],dis2[i]+m,-1);
}
for(int i=0;i<n;i++) cin>>board[i];
queue<pair<int,int>> Q;
queue<pair<int,int>> fire;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(board[i][j]=='F'){
fire.push({i,j});
dis1[i][j]=0;
}
if(board[i][j]=='J'){
Q.push({i,j});
dis2[i][j]=0;
}
}
}
while(!fire.empty()){
auto cur=fire.front(); fire.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(dis1[nx][ny]>=0 || board[nx][ny]=='#') continue;
dis1[nx][ny]=dis1[cur.X][cur.Y]+1;
fire.push({nx,ny});
}
}
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){
cout<<dis2[cur.X][cur.Y]+1;
return 0;
}
if(dis2[nx][ny]>=0 || board[nx][ny]=='#') continue;
if(dis1[nx][ny]!=-1&&dis1[nx][ny]<=dis2[cur.X][cur.Y]+1) continue;
dis2[nx][ny]=dis2[cur.X][cur.Y]+1;
Q.push({nx,ny});
}
}
cout<<"IMPOSSIBLE"<<'\n';
}
이건 혼자 삽질하다가 못풀어서 해설 봤다…
응용4 - 1차원에서의 BFS
#include <bits/stdc++.h>
using namespace std;
int vis[100001];
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
int N,K;
cin>>N>>K;
fill(vis,vis+100001,-1);
int d[4]={-1,1,2};
queue<int> Q;
Q.push(N);
vis[N]=0;
//아래 예외 케이스
if(N==K){
cout<<0;
return 0;
}
while(!Q.empty()){
auto cur=Q.front(); Q.pop();
for(int dir=0;dir<3;dir++){
int nx;
if(d[dir]==2) nx=d[dir]*cur;
else nx=cur+d[dir];
if(nx<0 || nx>100000) continue;
if(vis[nx]>=0) continue;
if(nx==K){
cout<<vis[cur]+1;
return 0;
}
Q.push(nx);
vis[nx]=vis[cur]+1;
}
}
}
이건 어쩌다보니 나 혼자 풀었는데 TC만 맞고 계속 틀렸대서 제미나이한테 물어봤다. 예외케이스를 하나 생각 안 해서 생긴 문제였다… TC를 잘 정의하는 것이 중요해보인다.
회고
아 오늘 왜이렇게 졸리냐.
- 픽업하고 공릉 픽업하고
- 집 가서 메일 보내기
- 그리고 할 일
오늘 인턴 마지막 보고서 제출했다! 나중에서야 알았는데 우리 조가 상당히 순항하고 나름 빠르게 보고서 끝난 거 같다. 조원들에게 감사할 뿐… 그리고 오늘 황당하고 웃긴 일 있었는데 이건 넘 잡담이니까 블로그에 적도록 하고… 오늘 근무시간에 엑셀 작업 하나 마무리하고 보고서랑 지원서 내고 선물 픽업 좀 했더니 너무 기력 딸려서 왁진긍 페탐만 했다. 하하 뒤늦게 그래도 오늘은 BFS 끝내야 후련할 거 같아서 끝냈고, DFS는 크게 다를 거 없으니까 내일 후딱 하고 회식 가려고 한다~~
BFS 너무 어려운데 적응 되겠지? 아직 워크북 문제 많으니까 잘 풀어보자…