[SWEA] C++ 1226. [S/W 문제해결 기본] 7일차 - 미로1(D3)

swb·2022년 11월 14일
0

SWEA

목록 보기
9/19

문제 바로가기

접근방법

  1. 미로는 대표적인 DFS/BFS 문제이다.
  2. 2인 지점에서 시작을 한다.
  3. 0인 곳만 밟고 다닌다.
  4. 3을 만나면 종료

풀이

#include <cstdio>
#include <iostream>
#include <queue>	
#define MAX 16
using namespace std;

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

int bfs(int y, int x) {
	queue<pair<int, int>> q;
	q.push(make_pair(y, x));

	while (!q.empty()) {
		y = q.front().first;
		x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (maze[ny][nx] == 3)
				return 1;

			if (ny >= 0 && ny < MAX && nx >= 0 && nx < MAX) {
				if (maze[ny][nx] == 0) {
					q.push(make_pair(ny, nx));
					maze[ny][x] = 1;
				}
			}
		}
	}
	return 0;
}

int main() {
	int test_case, start_y, start_x, tc;

	for (test_case = 1; test_case <= 10; test_case++) {
		cin >> tc;
		for (int i = 0; i < MAX; i++) {
			for (int j = 0; j < MAX; j++) {
				scanf("%1d", &maze[i][j]);

				if (maze[i][j] == 2) {
					start_y = i;
					start_x = j;
				}
			}
		}

		cout << "#" << tc << " " << bfs(start_y, start_x) << "\n";
	}
}
profile
개발 시작

0개의 댓글