Lee's Programming Practice

문제

* 해당 문제의 모든 저작권은 SWEA 측에 있으며 본 블로그는 학업 흔적을 남겨 학업 상향을 위한 블로그로 이익을 추구하지 않으며 SWEA 측의 약관을 위배하지 않음을 명시합니다.*

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

풀이

전형적인 그래프탐색 문제이며 BFS로 탐색하였다.

DFS는 경우 자원 소모가 크니까 사용하지 않았다.

소스 코드

// Library
#include <iostream>
#include <string>
#include <stack>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <cctype>
#include <set>
#include <string.h>
#include <string>

// std::
using namespace std;

// Test_case
int T, test_case;

// Value
int N;
int arr[16][16];
bool visited[16][16];

// Matrix direction
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

// Sturct
//struct st {
//};

bool isIn(int x, int y) {
	if (y >= 0 && y < 16 && x >= 0 && x < 16)
		return true;
	else
		return false;
}

bool BFS(int x, int y) {
	queue<pair<int, int>> q;
	q.push({ x, y });
	visited[x][y] = true;

	while (!q.empty()) {
		int ax = q.front().first;
		int ay = q.front().second;

		q.pop();

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

			if (!visited[nx][ny] && isIn(nx, ny) && (arr[nx][ny] == 0 || arr[nx][ny] == 3)) {
				if (arr[nx][ny] == 3) {
					return true;
				}
				q.push({ nx, ny });
				visited[nx][ny] = true;
			}
		}
	}

	return false;
}


// Main function
int main() {
	// cin, cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	// SWEA 양식
	T = 10;
	// cin >> T;
	for (test_case = 1; test_case <= T; test_case++) {
		memset(arr, 0, sizeof(arr));
		memset(visited, false, sizeof(visited));

		int ans = 0;

		cin >> N;
		for (int i = 0; i < 16; i++) {
			for (int j = 0; j < 16; j++) {
				scanf("%1d", &arr[i][j]);
			}
		}

		ans = BFS(1, 1) ? 1 : 0;

		cout << "#" << N << " " << ans << '\n';
	}
	
	return 0;
}