인프런 커뮤니티 질문&답변

주난이의 위치를 startPos에 입력받아 큐에 push한 후 방문 정보를 기록하고 범인의 위치는 어차피 BFS를 수행하는 과정에서 '#'을 만나면 범인의 위치이므로 필요 없다고 생각해서 버리기 위해 for문을 돌렸습니다.

문제의 예시를 봤을때, 주난이의 위치가 y성분 x성분 순으로 들어오고 인덱스가 1부터 시작하지만 저는 0부터 사용하므로 1씩 뺀 후 startPos에 할당했습니다.

혹시 제가 이해한 내용 중 잘못된 내용이 있을까요?

아 이해했습니다.

코드 상의 문제도 없어보이고 반례 몇개를 생각해서 집어넣어봤는데 잘 안되네요..

해당 부분 반례 찾는대로 다시 답변 드리겠습니다.

감사합니다.

반례 찾았습니다.

틀린 부분은 더미에 있었습니다.

더미는 char형입니다. 즉, 한 문자밖에 받지 못합니다. 하지만 이 문제의 범위는 300이기 때문에 3글자까지도 입력으로 올 수 있게 됩니다.

이렇게 한번 고쳐보시겠어요?

#include <iostream>
#include <queue>

using namespace std;

char map[304][304];
int visited[304][304];

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

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	cin >> N >> M;

	queue<pair<int, int>> q;
	queue<pair<int, int>> readyQ;

	pair<int, int> startPos;
	int temp;
	cin >> temp;
	startPos.first = temp - 1;
	cin >> temp;
	startPos.second = temp - 1;
	
	q.push(startPos);
	visited[startPos.first][startPos.second] = 1;

	for (int i = 0; i < 2; i++)
	{
    int aa;  
		cin >> aa;
	}
	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> map[i][j];
		}
	}

	int ans = 0;

	while (true)
	{
		ans++;

		while (!readyQ.empty())
		{
			q.push(readyQ.front());
			readyQ.pop();
		}

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

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

				if (newY < 0 || newY >= N || newX < 0 || newX >= M)
					continue;
				if (visited[newY][newX])
					continue;

				if (map[newY][newX] == '0')
				{
					q.push({ newY, newX });
					visited[newY][newX] = 1;
				}
				else if (map[newY][newX] == '1')
				{
					readyQ.push({ newY, newX });
					visited[newY][newX] = 1;
				}
				else if (map[newY][newX] == '#')
				{
					cout << ans;
					return 0;
				}
			}
		}
	}

	return 0;
}

이해했습니다! 감사합니다!