1226. [S/W 문제해결 기본] 7일차 - 미로1

1. BFS, DFS를 사용해서 풀면되는 기본문제 중 하나이다.

2. BFS를 통해 문제를 해결하였다.

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD

SW Expert Academy

 

소스코드 보기

#include <stdio.h>
#include <queue>
#define MAX_NODE 16
using namespace std;

int map[16][16];
int visited[16][16];
int beginX, beginY, endX, endY;
int dx[] = { 0, 0, -1, 1 };
int dy[] = { 1, -1, 0, 0 };
bool bfs() 
{
	queue<pair<int, int>> que;
	visited[beginY][beginX] = 1;
	que.push(make_pair(beginY, beginX));

	while (!que.empty()) {
		int queSize = que.size();
		for (int i = 0; i < queSize; i++) {
			int curx = que.front().second;
			int cury = que.front().first;
			que.pop();
			if (curx == endX && cury == endY) {
				return true;
			}
			for (int j = 0; j < 4; j++) {
				int nx = curx + dx[j];
				int ny = cury + dy[j];
				if (nx < 0 || ny < 0 || nx >= MAX_NODE || ny >= MAX_NODE || visited[ny][nx] || map[ny][nx] == 1) {
					continue;
				}
				que.push(make_pair(ny, nx));
				visited[ny][nx] = 1;
			}
		}
	}
	return false;
}

int main()
{
	for (int k = 1; k <= 10; k++) {
		int n;
		scanf("%d", &n);
		for (int i = 0; i < MAX_NODE; i++) {
			for (int j = 0; j < MAX_NODE; j++) {
				char ch;
				visited[i][j] = 0;
				scanf(" %c", &ch);
				map[i][j] = ch - '0';
				if (map[i][j] == 2) {
					beginX = j;
					beginY = i;
				}
				else if (map[i][j] == 3) {
					endX = j;
					endY = i;
				}
			}
		}
		printf("#%d %d\n" ,n , bfs() ? 1 : 0);
	}
}