백준 13460번 구슬 탈출2

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

13460번: 구슬 탈출 2

 

 

 

 

<접근방법>

최소, 탐색 이라는 키워드로 bfs에 대한 느낌을 받을 수 있었습니다.

처음에 이동은 바로 감이 잡혔으나 방문은 잘모르겠단 생각을 했습니다.

 

방문체크는 4차원 배열로 했습니다.

처음에 이 방법을 떠올리는 회로는 모르겠으나,

빨간 공, 파란 공이 전 상태의 좌표와 똑같다면 중복방문이며, 또 다시 확인할 가치가 없다는 것을

알 수 있었습니다.

 

파란공만 홀에 빠졌을 때와 두 개 공이 같이 홀에 빠졌을 때의 처리에 있어

위치도 중요합니다.

 

라운드 체크는 구조체에 변수를 따로 만들어서 했습니다.

 

그 외 다른 모듈의 구현에서 배울 점이 많았습니다.

 

 

---

 

 

 

<코드>

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct point {
	int y, x;
};

struct bead {
	int ry, rx, by, bx, cnt;
};

int n, m;
char map[10][10];
int visit[10][10][10][10];
int dy[4] = {0, 0, -1, 1};
int dx[4] = { -1, 1, 0, 0 };//서동북남
point sr, sb;
queue<bead> q;

void move(int &y, int &x, int &c, int d) {
	while(map[y+dy[d]][x+dx[d]] != '#' && map[y][x] != 'O'){
		y += dy[d];
		x += dx[d];
		c += 1;
	}
}

void bfs() {
	q.push({sr.y, sr.x, sb.y, sb.x, 0});
	visit[sr.y][sr.x][sb.y][sb.x] = 1;

	while (!q.empty()) {
		bead t = q.front();
		q.pop();

		if (t.cnt > 10) {
			printf("-1\n");
			exit(0);
		}
		if (map[t.ry][t.rx] == 'O') {
			printf("%d\n", t.cnt);
			exit(0);
		}
		
		for (int i = 0; i < 4; i++) {
			//next설정
			int nry = t.ry, nrx = t.rx, nby = t.by, nbx = t.bx;
			int ncnt = t.cnt+1;
			int rc=0, bc=0;

			move(nry, nrx, rc, i);
			move(nby, nbx, bc, i);

			//조건
			if (map[nby][nbx] == 'O') continue;

			//조건
			if (nry == nby && nrx == nbx) {
				if (rc > bc) {
					nry -= dy[i];
					nrx -= dx[i];
				}
				else {
					nby -= dy[i];
					nbx -= dx[i];
				}
			}
			//조건
			if (visit[nry][nrx][nby][nbx] == 1) continue;
			visit[nry][nrx][nby][nbx] = 1;
			q.push({nry, nrx, nby, nbx, ncnt});//상태를 저장
		}
	}
	
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf(" %c", &map[i][j]);
			char t = map[i][j];
			if (t == 'R') {
				sr = { i, j };
			}
			else if(t == 'B'){
				sb = { i, j };
			}
		}
	}

	bfs();
	printf("-1\n");
}

 

 

---

 

 

<느낀 점>

-while문은 잘쓰면 찌린다.

-연산, 역연산