출처 : https://school.programmers.co.kr/learn/courses/30/lessons/150365
풀이 방법
일반적인 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;
}
'Algorithm' 카테고리의 다른 글
[백준] 백조의 호수 3197번 (c++) (0) | 2025.01.01 |
---|---|
[백준] 구간 합 구하기 2042번 (c++) 세그먼트트리 (0) | 2025.01.01 |
[프로그래머스] 도넛과 막대 그래프 (c++) 엣지 케이스 (0) | 2024.12.29 |
[코드트리] 메두사와 전사들 (1) | 2024.12.28 |
[프로그래머스] 수레 움직이기 C++ (0) | 2024.12.24 |