문제 링크(Link)
https://www.acmicpc.net/problem/11559
문제 해결(Solution)
1. 기본적인 BFS or DFS와 구현을 물어보는 문제.
주의할 점 || 생각해볼 점(Caution || Consideration)
1. 몇 번 블럭이 삭제되는 지를 물어보는 문제가 아니고 몇 번 연쇄되는 지를 물어보는 문제임을 숙지해야한다.
참고(Reference)
-
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
explanation in vjerksen.tistory.com | |
*/ | |
#include<iostream> | |
#include<cstdio> | |
#include<string> | |
#include<cstring> | |
#include<algorithm> | |
#include<queue> | |
#include<set> | |
#include<ctime> | |
#include<vector> | |
#include<stack> | |
using namespace std; | |
int N,ans; | |
char a[15][8]; | |
int row_move[]={-1,1,0,0}; | |
int col_move[]={0,0,-1,1}; | |
void fall(){ | |
for(int j=0;j<6;j++){ | |
for(int i=11;i>=0;i--){ | |
if(a[i][j]!='.'){ | |
bool flag=false; | |
int idx; | |
for(int k=i+1;k<12;k++){ | |
if(a[k][j]!='.'){ | |
flag=true; | |
idx=k; | |
break; | |
} | |
} | |
if(flag){ | |
int moving = idx-i-1; | |
swap(a[i+moving][j],a[i][j]); | |
} | |
else{ | |
swap(a[i][j],a[11][j]); | |
} | |
} | |
} | |
} | |
} | |
bool bfs(int row,int col){ | |
bool visit[14][8]; | |
memset(visit,false,sizeof(visit)); | |
queue<pair<int,int> > q; | |
queue<pair<int,int> > delQ; | |
int comp=1; | |
visit[row][col]=true; | |
q.push({row,col}); | |
delQ.push({row,col}); | |
while(!q.empty()){ | |
int crow = q.front().first; | |
int ccol = q.front().second; | |
q.pop(); | |
for(int i=0;i<4;i++){ | |
int nrow = crow+row_move[i]; | |
int ncol = ccol+col_move[i]; | |
if(nrow<0||nrow>=12||ncol<0||ncol>=6) | |
continue; | |
if(a[crow][ccol]!=a[nrow][ncol]) | |
continue; | |
if(visit[nrow][ncol]) | |
continue; | |
visit[nrow][ncol]=true; | |
q.push({nrow,ncol}); | |
delQ.push({nrow,ncol}); | |
comp++; | |
} | |
} | |
if(comp>=4){ | |
while(!delQ.empty()){ | |
int x = delQ.front().first; | |
int y = delQ.front().second; | |
delQ.pop(); | |
a[x][y]='.'; | |
} | |
return true; | |
} | |
else | |
return false; | |
} | |
int main(){ | |
for(int i=0;i<12;i++){ | |
scanf("%s",a[i]); | |
} | |
while(true){ | |
bool flag=false; | |
for(int i=11;i>=0;i--){ | |
for(int j=0;j<6;j++){ | |
if(a[i][j]!='.'){ | |
if(bfs(i,j)){ | |
flag=true; | |
} | |
} | |
} | |
} | |
// caution 1 | |
if(flag){ | |
ans++; | |
fall(); // fall blocks. | |
} | |
else{ | |
break; | |
} | |
} | |
printf("%d",ans); | |
return 0; | |
} |
※ 정확하고 부드러운 태클은 언제나 환영입니다.
'Problem Solving > 그래프' 카테고리의 다른 글
BOJ 4792 - 레드 블루 스패닝 트리 (0) | 2018.03.08 |
---|---|
BOJ 1761 - 정점들의 거리 (0) | 2017.10.06 |
SW Expert Academy 1795 - 인수의 생일 파티 (0) | 2017.09.08 |
codeground practice - 최소 신장 트리 (0) | 2017.07.14 |
BOJ 14502 - 연구소 (0) | 2017.07.12 |