Algorithm

[프로그래머스] 미로 탈출 명령어 (c++)

salmon16 2024. 12. 31. 16:04

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/150365

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

풀이 방법

일반적인 dfs로 풀이할 수 있다.

방향의 우선순위를 d l r u로 dy, dx를 설정해 사전순으로 dfs를 방문하도록 설정을 했다.

또 사전순으로 탐색을 했기 때문에 만약 도착지에 도달을 하게 된다면, 탐색을 멈추고 답을 도출했다.

 

또 시간을 줄이기 위해 K에서 출발지와 도착지의 거리의 차가 2로 나누어 떨어지지 않는다면, 도착 불가능한 경우이므로 제거했다.

 

또한 중복 탐색을 방지하기 위해, y, x지점에 cnt의 횟수를 가진 경우의 중복을 visited로 체크해서 중복 탐색을 방지했다.

 

#include <string>
#include <vector>
#include <memory.h>
#include <iostream>
#include <math.h>
using namespace std;


int dy[4] = {1, 0, 0, -1}; //d l r u순
int dx[4] = {0, -1, 1, 0};
char dir[4] = {'d', 'l', 'r', 'u'};
int visited[51][51][2501];
pair<int, int> start_p, end_p;
int N, M, K;
string ans = "impossible";
void dfs(int cnt, int y, int x, string path) {        
    if (cnt > K) return ;
    visited[y][x][cnt] = 1;
    if (cnt == K) {
        if (y == end_p.first && x == end_p.second) {
            if (ans == "impossible") ans = path;            
            return ;
        }
        else {
            return ;
        }
    }
    if (ans != "impossible") return ; // 답을 찾은 경우 탐색 중지
    for (int i = 0;i < 4;i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
        if (visited[ny][nx][cnt + 1] == 1) continue;
        dfs(cnt + 1, ny, nx, path + dir[i] );
    }
} 
string solution(int n, int m, int x, int y, int r, int c, int k) {    
    memset(visited, 0, sizeof(visited));
    N = n, M = m, K = k;
    start_p.first = x-1, start_p.second = y-1, end_p.first = r-1, end_p.second = c-1;
    if ((k - abs(x - r) + abs(y - c)) % 2 == 0) 
        dfs(0, x-1, y-1, "");
    return ans;
}