[백준 17070번] 파이프 옮기기 1 풀이 _ C++ 삼성 A형 기출 문제

삼성 A형 기출문제인 파이프옮기기 1 입니다.

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

 

문제에서 절대 빠뜨리지 말고 봐야 하는 부분!!

 

 

 

이거 저만 발견 못 본거겠죠? 하..ㅋㅋ 앞으로 문제를 더 제대로 읽어야 겠네요.

 

옮기는 건 BFS 방식을 사용해서 가로, 세로, 대각선 방향으로 이동하면 됩니다. 현재 놓여진 방향에 따라서.

저는 위 형광펜 문장을 놓쳐서 엄청 오래 풀었어요.

대각선일 때 체크해야 할 칸들이 더 있음.

 

 

대각선 방향 이동 시 체크할 칸이 더 있다.

 

가로나 세로는 그냥 바로 이동했을 때 놓여지는 칸만 빈칸인지 체크하면 되는데 대각선은 이동할 칸 외에도 주변 칸도 체크해야 해요.

 

#include <iostream>
#include <queue>
using namespace std;

int map[17][17];// 1~16 인덱스 사용
int n, ans;
int dx[3] = {0, +1, +1}; //가로 대각선 세로
int dy[3] = { +1, +1, 0 };

struct info {
	int x, y, d;
	//방향은 0, 1, 2 순서대로 가로, 대각선, 세로
};

queue<info>q;

void move(int x, int y, int d, int i) {
	int nx = x + dx[i];
	int ny = y + dy[i];
	int nd = i;
	if (map[nx][ny] == 0 && nx > 0 && nx <= n && ny > 0 && ny <= n) {
		if (i == 1) {//대각선은 추가 체크
			if (map[nx - 1][ny] == 1 || map[nx][ny - 1] == 1)
				return;
		}
		q.push({ nx, ny, nd });
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}
	q.push({ 1,2,0 });
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int d = q.front().d;
		q.pop();
		if (x == n && y == n)
			ans++;
		if (d == 0) { //가로
			for (int i = 0; i < 2; i++) { //0,1로 이동
				move(x, y, d, i);
			}
		}
		else if (d == 1) {//대각선
			for (int i = 0; i < 3; i++) { //0,1,2로 이동
				move(x, y, d, i);
			}
		}
		else {//아래
			for (int i = 1; i < 3; i++) { //1,2로 이동
				move(x, y, d, i);
			}
		}
	}
	cout << ans;
	return 0;
}