[SWEA] 1953번: ［모의 SW 역량테스트］ 탈주범 검거 (Unrated) - C++ 풀이

BFS

💾 메모리: 6,016 KB, 시간: 6 ms, 코드길이: 1,916 Bytes📅 2026-04-09 03:33

문제 링크

코드 (C++)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

struct pos
{
	int y, x;
};
pos vect[4]{ // 상하좌우
	{-1,0}, {1,0},{0,-1},{0,1}
}; 

pos pipe[8][4] = {
	{},
	{ {1,0},{-1,0},{0,1},{0,-1} },	//1. 상하좌우
	{ {1,0},{-1,0} },				//2
	{ {0,1},{0,-1} },				//3
	{ {-1,0},{0,1} },				//4
	{ {1,0},{0,1} },				//5
	{ {1,0},{0,-1} },				//6
	{ {-1,0},{0,-1} }				//7
};
int pLen[8] = {0,4,2,2,2,2,2,2};
int map[50][50];
int dist[50][50];
int N, M, R, C, L;

bool connect(pos s, pos e) {
	int sId = map[s.y][s.x];
	int eId = map[e.y][e.x];
	bool sCon=false, eCon=false;
	for (int i = 0; i < pLen[sId]; i++)
	{
		if (s.y + pipe[sId][i].y == e.y && s.x + pipe[sId][i].x == e.x)
			sCon = true;
	}
	for (int i = 0; i < pLen[eId]; i++)
	{
		if (e.y + pipe[eId][i].y == s.y && e.x + pipe[eId][i].x == s.x)
			eCon = true;
	}

	if (sCon && eCon) return true;
	else return false;
}


int bfs(pos st, int limit) {
	queue<pos> q;
	q.push(st);
	dist[st.y][st.x] = 1;
	int cnt = 1;
	while (!q.empty())
	{
		pos s = q.front();
		q.pop();
		if (dist[s.y][s.x] == limit)
			break;
		for (int i = 0; i < 4; i++)
		{
			int ny = s.y + vect[i].y;
			int nx = s.x + vect[i].x;
			if (ny < 0 || nx < 0 || ny >= N || nx >= M)
				continue;
			if (connect(s, { ny,nx }) && dist[ny][nx] == 0) {
				q.push({ ny, nx });
				dist[ny][nx] = dist[s.y][s.x]+1;
				cnt++;
			}
		}
	}
	return cnt;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("sample_input_2.txt", "r", stdin);
	// 0 0 5 3 6 0  / st ()2,1
	// 0 0 2 0 2 0
	// 3 3 1 3 7 0
	// 0 0 0 0 0 0
	// 0 0 0 0 0 0
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++)
	{
		cin >> N >> M >> R >> C >> L;
		for (int y = 0; y < N; y++)
			for (int x = 0; x < M; x++)
				cin >> map[y][x];

		memset(dist, 0, sizeof(dist));

		pos st = { R,C };
		cout << "#" << tc << " " << bfs(st, L) << "\n";
	}
}