[프로그래머스] 게임 맵 최단거리 - LEVEL2

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/1844

✍️ 문제 풀이

최단 경로를 구하는 문제의 경우 BFS 방식이 효율적이라고 하여, 해당 문제는 BFS 방식으로 풀었다.

1) 방문한 칸의 (x좌표, y좌표, 누적 이동 칸수)를 저장하는 tuple들을 저장할 큐를 선언한다.
2) 첫 칸에 대해 방문 처리를 하고 큐에 삽입한다.
3) 큐의 최전방 노드를 삭제하고, 이에 저장된 칸과 인접한 칸들을 전부 큐에 삽입한다. 단 해당 칸은 이전에 방문한 적 없고, 그 값이 0이 아니어야 한다. (이동 가능 조건)
4) 목표 위치에 도달하거나, 큐가 전부 빌 때까지 3)을 반복 실행한다.

🖥️ 풀이 코드

효율성 테스트 실패

#include <bits/stdc++.h>

using namespace std;

queue<tuple<int, int, int>> q;	// tuple : 세 개의 변수 저장할 수 있는 구조 (방문한 칸의 y좌표, x좌표, 누적 칸수)

int BFS(vector<vector<int>> maps, int start_y, int start_x)
{
	int answer = 1;
	int count = 1;

	int n, m;
	n = maps[0].size();		// 맵 가로 길이
	m = maps.size();		// 맵 세로 길이

	vector<bool> set_bool(n, false);	// visited 초기화 하기 위한 bool 배열
	vector<vector<bool>> visited(m, set_bool); // 각 노드 방문 여부 저장하는 bool 변수 배열의 배열

	// 첫 위치 방문 처리 하고 큐에 삽입
	visited[start_y][start_x] = true;
	q.push(tuple<int, int, int>(start_y, start_x, 1));

	while (!q.empty())
	{
		int x, y, count;
		y = get<0>(q.front());	// 가장 앞에 있는 노드의 tuple 중 첫번째 값 반환 (y좌표)
		x = get<1>(q.front());	// 가장 앞에 있는 노드의 tuple 중 두번째 값 반환 (x좌표)
		count = get<2>(q.front()); // 가장 앞에 있는 노드의 tuple 중 세번째 값 반환 (누적 칸수)
		visited[y][x] = true;	// 큐에서 빼내면서 방문 처리
		q.pop();

		// 현재 위치의 왼쪽 노드 큐에 추가
		if (x > 0)
		{
			if (maps[y][x - 1] != 0 && visited[y][x - 1] == false)
				q.push(tuple<int, int, int>(y, x - 1, count + 1));	// 다음 노드의 누적 칸수 = 이전 노드의 누적 칸수 + 1
		}

		// 현재 위치의 오른쪽 노드 큐에 추가
		if (x < n - 1)
		{
			if (maps[y][x + 1] != 0 && visited[y][x + 1] == false)
				q.push(tuple<int, int, int>(y, x + 1, count + 1));
		}

		// 현재 위치의 위쪽 노드 큐에 추가
		if (y > 0)
		{
			if (maps[y - 1][x] != 0 && visited[y - 1][x] == false)
				q.push(tuple<int, int, int>(y - 1, x, count + 1));
		}

		// 현재 위치의 아래쪽 노드 큐에 추가
		if (y < m - 1)
		{
			if (maps[y + 1][x] != 0 && visited[y + 1][x] == false)
				q.push(tuple<int, int, int>(y + 1, x, count + 1));
		}

		if (y == m - 1 && x == n - 1)
			return count;
		else if (q.empty())
			return -1;
	}
}

int solution(vector<vector<int> > maps)
{
	int answer = BFS(maps, 0, 0);
	return answer;
}

처음에 정확성 테스트는 통과했지만 효율성 테스트를 통과하지 못했는데, 어떤 부분이 문제인지 찾아보니 방문 처리 하는 순서의 문제였다.

효율성 테스트를 통과하지 못했을 때는 방문 처리를 큐에서 삭제하면서 방문 처리를 해주었다. 위 그림과 같은 경우를 보면 큐에 10(1)과 10(2)이 들어있는 상태에서 11을 먼저 큐에 넣고, 10(1)을 큐에서 빼고 방문 처리한다. 이후 또 11을 큐에 넣고, 10(2)를 큐에서 빼고 방문 처리한다. 그 다음에 11을 큐에서 뺄 때가 돼서야 11의 방문 처리가 된다. 이처럼 큐에서 삭제하면서 방문 처리를 할 경우 같은 칸이 중복 삽입 되는 경우가 발생한다.

효율성 테스트 통과

#include <bits/stdc++.h>

using namespace std;

queue<tuple<int, int, int>> q;	// tuple : 세 개의 변수 저장할 수 있는 구조 (방문한 칸의 y좌표, x좌표, 누적 칸수)

int BFS(vector<vector<int>> maps, int start_y, int start_x)
{
	int answer = 1;
	int count = 1;

	int n, m;
	n = maps[0].size();		// 맵 가로 길이
	m = maps.size();		// 맵 세로 길이

	vector<bool> set_bool(n, false);	// visited 초기화 하기 위한 bool 배열
	vector<vector<bool>> visited(m, set_bool); // 각 노드 방문 여부 저장하는 bool 변수 배열의 배열

	// 첫 위치 방문 처리 하고 큐에 삽입
	visited[start_y][start_x] = true;
	q.push(tuple<int, int, int>(start_y, start_x, 1));

	while (!q.empty())
	{
		int x, y, count;
		y = get<0>(q.front());	// 가장 앞에 있는 노드의 tuple 중 첫번째 값 반환 (y좌표)
		x = get<1>(q.front());	// 가장 앞에 있는 노드의 tuple 중 두번째 값 반환 (x좌표)
		count = get<2>(q.front()); // 가장 앞에 있는 노드의 tuple 중 세번째 값 반환 (누적 칸수)
		q.pop();
        
		// 현재 위치의 왼쪽 노드 큐에 추가
		if (x > 0 && maps[y][x - 1] != 0 && visited[y][x - 1] == false)
		{
			q.push(tuple<int, int, int>(y, x - 1, count + 1));	// 다음 노드의 누적 칸수 = 이전 노드의 누적 칸수 + 1
			visited[y][x - 1] = true;	// 큐에 집어 넣으면서 방문 처리
		}

		// 현재 위치의 오른쪽 노드 큐에 추가
		if (x < n - 1 && maps[y][x + 1] != 0 && visited[y][x + 1] == false)
		{
			q.push(tuple<int, int, int>(y, x + 1, count + 1));
			visited[y][x + 1] = true;
		}

		// 현재 위치의 위쪽 노드 큐에 추가
		if (y > 0 && maps[y - 1][x] != 0 && visited[y - 1][x] == false)
		{
			q.push(tuple<int, int, int>(y - 1, x, count + 1));
			visited[y - 1][x] = true;
		}

		// 현재 위치의 아래쪽 노드 큐에 추가
		if (y < m - 1 && maps[y + 1][x] != 0 && visited[y + 1][x] == false)
		{
			q.push(tuple<int, int, int>(y + 1, x, count + 1));
			visited[y + 1][x] = true;
		}

		if (y == m - 1 && x == n - 1)
			return count;
		else if (q.empty())
			return -1;
	}
}

int solution(vector<vector<int> > maps)
{
	int answer = BFS(maps, 0, 0);
	return answer;
}

반면 큐에 넣자마자 방문 처리를 하게 되면 10(1)을 큐에서 빼고 11을 넣을 때 11에 대한 방문 처리를 하기 때문에 10(2)를 큐에서 뺄 때는 이미 11의 방문 처리가 되어있어 큐에 추가할 수 없게 된다.