[Programmers] 1844 게임 맵 최단거리 (C++)

문제

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

프로그래머스

 

풀이

문제를 읽으면 Flood fill을 사용하는 문제임을 알 수 있다. 잠시 Flood fill을 알아보면,

Flood fill이란? 

2차원 배열(혹은 다차원 배열)에서 주어진 시작점과 연결된 영역 전체를 찾아서 특정 값(색상 등)으로 바꾸는 알고리즘

 

Flood fill을 이용한 BFS의 기본적인 예제 문제이다. (0, 0)에서 (n-1, m-1)까지의 최단 경로를 찾아야 한다. 프로그래머스 특성상 다음의 처리만 잘 해주면 된다.

1. 방문할 수 없는 경우 -1 예외 처리
2. 프로그래머스 환경이므로 solution함수 안에서 N, M 초기화하기

 

코드

#include<iostream>
#include<queue>
#include<vector>
#define IN(Y, X) (Y < N && Y >= 0 && X < M && X >= 0)
#define FAST_IO cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define F first
#define S second
using namespace std;
typedef pair<int, int> PII;

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

bool visit[100][100];
queue<PII> que;



int solution(vector<vector<int>> maps) {
	int answer = -1;
    
    int N = maps.size();
    int M = maps[0].size();

	que.push({ 0, 0 });
	visit[0][0] = true;

	while (!que.empty()) {
		PII cur = que.front();
		que.pop();
		int cy = cur.F;
		int cx = cur.S;

		if (cy == N - 1 && cx == M - 1) return maps[cy][cx];

		for (int i = 0; i < 4; i++) {
			int ny = cy + dy[i];
			int nx = cx + dx[i];
			if (IN(ny, nx) && maps[ny][nx] == 1 && !visit[ny][nx]) {
				maps[ny][nx] = maps[cy][cx] + 1; // cnt 
				visit[ny][nx] = true;
				que.push({ ny, nx });
			}
		}
	}
	return answer;
}