백준 통나무

문제

1*3 통나무를 목적지까지 옮기는 문제

조건

• 통나무는 1 * 3 모양임
• 한번의 움직임으로 상, 하, 좌, 우, 돌리기 가능
• 돌리기를 시도할 때 무조건 주변의 3*3 칸이 비워져 있어야 함

ex)
***
BBB 돌리기 가능
***

***
BBB 돌리기 불가능
*1*

설명

튜플 사용 (int 3칸짜리)

튜플이란?

3칸 이상의 pair같은 느낌
구조체를 만들지 않고 간단하게 구조체 느낌으로 사용 가능하다!

여기서는 int 3칸으로 통나무 가운데 x좌표, y좌표, 가로세로를 나타내는 한칸

• 가로는 0
• 세로는 1

1. 맨 처음 findB() findE() 로 출발지점, 도착지점을 위의 전역변수 튜플로 저장해둔다

2. set 형성

set이란?

순서, 중복이 없는 리스트를 말함

#include <set>

set<tuple<int,int,int> >s;

3. queue에는 위의 튜플과 시간을 나타내는 정수를 pair로 넣게된다

• 만약 정답과 같은 위치라면 종료

• set에 현재 위치가 저장돼있지 않으면 insert후 진행함

• 다양한 형태 가능한데로 큐에 집어넣음,,

코드

#include <stdio.h>
#include <set>
#include <tuple>
#include <queue>
using namespace std;
queue<pair<tuple<int,int,int>,int > >q;
set<tuple<int,int,int> >s;

tuple<int,int,int> ans;
tuple<int,int,int> start;
int n;
char map[51][51];

void findB(){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(map[i][j]=='B'){ //B 발견 
				if(j+1<n&&map[i][j+1]=='B'){ // 가로 모양
					get<0>(start)=i;
					get<1>(start)=j+1;
					get<2>(start)=0;
				}else{ // 세로 모양 
					get<0>(start)=i+1;
					get<1>(start)=j;
					get<2>(start)=1;
				}
				return;
			}
			
		}
	}
}

void findE(){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(map[i][j]=='E'){
				if(j+1<n&&map[i][j+1]=='E'){
					get<0>(ans)=i;
					get<1>(ans)=j+1;
					get<2>(ans)=0;
				}else{
					get<0>(ans)=i+1;
					get<1>(ans)=j;
					get<2>(ans)=1;

				}
				return;
			}
			
		}
	}
}

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			scanf(" %c",&map[i][j]);
		}
	}
	findB();
	findE();
//	printf("%d %d %d\n\n",get<0>(ans),get<1>(ans),get<2>(ans));
	q.push(make_pair(start,0));
	while(!q.empty()){
	
		if(q.front().first==ans){
			printf("%d\n",q.front().second);
//			printf("%d %d %d",get<0>(q.front().first),get<1>(q.front().first),get<2>(q.front().first));
			return 0;
		}
		if(s.find(q.front().first)==s.end()){
			s.insert(q.front().first);
			int x = get<0>(q.front().first);
			int y = get<1>(q.front().first);
			int dir=get<2>(q.front().first);
			int time = q.front().second;
//			printf("%d %d %d %d\n",x,y,dir,time);
			if(dir==0){ //가로
				int tmp=0;
				int tmp2=0;
				if(x>0){
					for(int i=y-1;i<=y+1;i++){
						if(map[x-1][i]=='1'){
							tmp++;
						}
					}
					if(tmp==0){
						q.push(make_pair(make_tuple(x-1,y,dir),time+1));
					}
				}else{
					tmp=9;
				}
				if(x+1<n){
					for(int i=y-1;i<=y+1;i++){
						if(map[x+1][i]=='1'){
							tmp2++;
						}
					}
					if(tmp2==0){
						q.push(make_pair(make_tuple(x+1,y,dir),time+1));
					}
				}else{
					tmp2=9;
				}
				if(tmp==0&&tmp2==0){
					q.push(make_pair(make_tuple(x,y,1),time+1));
				}
				if(y-2>=0&&map[x][y-2]!='1'){
					q.push(make_pair(make_tuple(x,y-1,0),time+1));
				}
				if(y+2<n&&map[x][y+2]!='1'){
					q.push(make_pair(make_tuple(x,y+1,0),time+1));
				}
			}else{
				int tmp=0;
				int tmp2=0;
				if(y>0){
					for(int i=x-1;i<=x+1;i++){
						if(map[i][y-1]=='1'){
							tmp++;
						}
					}
					if(tmp==0){
						q.push(make_pair(make_tuple(x,y-1,dir),time+1));
					}
				}else{
					tmp=9;
				}
				if(y+1<n){
					for(int i=x-1;i<=x+1;i++){
						if(map[i][y+1]=='1'){
							tmp2++;
						}
					}
					if(tmp2==0){
						q.push(make_pair(make_tuple(x,y+1,dir),time+1));
					}
				}else{
					tmp2=9;
				}
				if(tmp==0&&tmp2==0){
					q.push(make_pair(make_tuple(x,y,0),time+1));
				}
				if(x-2>=0&&map[x-2][y]!='1'){
					q.push(make_pair(make_tuple(x-1,y,dir),time+1));
				}
				if(x+2<n&&map[x+2][y]!='1'){
					q.push(make_pair(make_tuple(x+1,y,dir),time+1));
				}
			}
		}
		
		q.pop();
	}
	printf("0");
}