SWEA-1211 Ladder2

입력을 받은뒤 0행에서의 해당 출발점의 값이 1이면 queue에 push한뒤 순차적으로 좌, 우, 아래 순서로 찾았다. ch 배열을 활용해 우측으로 방향을 진행하는 경우엔 다음 방향을 찾을 때 이미 방문한 곳을 방문하지 않게 해서 좌측에 방문한 곳을 탐색하지 않도록 했다. 도착점에 도착한 경우 가장 큰 시작점을 찾게 해주었다.

#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

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

int arr[110][110];
int ch[110][110];

int main(){
	for(int T=0; T<10; T++){
		int tc;
		cin>>tc;
		
		queue<pair<int, int> > q;
		
		for(int i=0; i<100; i++){
			for(int j=0; j<100; j++){
				cin>>arr[i][j];
			}
		}
		int val=2147000000;
		int yval=-1;
		for(int i=0; i<100; i++){
			if(arr[0][i]==1){
				memset(ch, 0, sizeof(ch));
				q.push(make_pair(0, i));
				ch[0][i]=1;
				int cnt=0;
			
				while(!q.empty()){
					int x=q.front().first;
					int y=q.front().second;
					
					q.pop();
					
					cnt++;
					
					if(x==99){
						if(val>=cnt){
							val=cnt;
							yval=i;
						}
						break;
					}
					
					for(int k=0; k<3; k++){
						int nx=x+dx[k];
						int ny=y+dy[k];
						if(arr[nx][ny]==1&&ch[nx][ny]==0){
							q.push(make_pair(nx, ny));
							ch[nx][ny]=1;
							break;
						}
					}
					
				}
			}
		}
		
		cout<<"#"<<tc<<" "<<yval<<'\n';
	}
	return 0;
}