BFS(5) - 확장 게임, 등...

이제 0x09강 BFS 문제집을 다 풀어가네요... 이제 좀 감이 잡히는 것 같습니다

---

https://www.acmicpc.net/problem/16920

16920번: 확장 게임

코드를 다 짜고 테스트케이스를 보다보니 좀 이상한 부분이 있었다. 그래서 질문 게시판을 살펴보았는데 문제의 표현이 애매해서 코드를 잘못 짠 것을 깨닫고 다시 짰다. 큐나 다른 자료형에서도 [10] 같은 기호를 활용할 수 있다는 것을 배웠다.

 

https://www.acmicpc.net/board/view/89992

글 읽기 - 문제 지문이 잘못되었습니다. 수정 요청합니다.

 

#include <bits/stdc++.h>
using namespace std;
int n,m,player;
int s[12];
int ans[12];
int board[1003][1003];
int vis[1003][1003];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
queue<tuple<int,int,int>> Q[10];

int main() {
    cin>>n>>m>>player;
    for(int i=1;i<=player;i++){
        cin>>s[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
        	char temp; cin>>temp;
        	if(temp=='.') board[i][j]=1;
            else if(temp=='#') board[i][j]=0;
            else{
            	board[i][j]=0;
            	vis[i][j]=true;
            	Q[temp-'0'].push(make_tuple(i,j,0));
            	ans[temp-'0']++;
			}
        }
    }

    while(1){
    	bool isExtend=false;
    	for(int p=1;p<=player;p++){
    		queue<tuple<int,int,int>> nxtq;
    		while(!Q[p].empty()){
    			auto cur = Q[p].front(); Q[p].pop();
    			int curY,curX,cnt;
    			tie(curY,curX,cnt)=cur;
    			
    			//주어진 횟수만큼 bfs를 했으면 
    			if(cnt>=s[p]){
    				nxtq.push(make_tuple(curY,curX,0));
    				continue;
				}
    			
    			for(int dir=0;dir<4;dir++){
    				int ny=curY+dy[dir];
    				int nx=curX+dx[dir];
    				if(nx<0||ny<0||nx>=m||ny>=n) continue;
    				if(!board[ny][nx] || vis[ny][nx]) continue;
    				Q[p].push(make_tuple(ny,nx,cnt+1));
    				vis[ny][nx]=true; ans[p]++;
    				isExtend=true;
				}
			}
			Q[p]=nxtq;
		}
		if(!isExtend) break;
	}
    
    for(int i=1;i<=player;i++) cout<<ans[i]<<' ';
    return 0;
}

---

https://www.acmicpc.net/problem/11967

11967번: 불켜기

https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

https://www.acmicpc.net/problem/9328

9328번: 열쇠

 

지금 풀기엔 좀 힘들어서 나중에 정리하기로...