문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/250134
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
최근에 나온 따끈따끈한 문제.
생각할 경우의 수가 많다 보니까, 빡구현 문제에 속하는 것 같다.
1시간 제 한 시간 안에는 푸는 것에는 실패했지만,
인터넷 도움 없이 스스로 풀어냈다.
문제 핵심 및 풀이
제한사항을 통해 유형 파악
제한사항을 통해 문제의 유형을 파악하는 것이 첫 번째 관문이라고 생각한다.
N x M 맵의 최대 크기를 살펴보면, 아무리 커봤자 4 x 4 가 최대 크기이다.
즉, O(N^3)을 하던 O(N!)을 하던 시간초과가 나지 않을 만큼 충분히 작다는 것이다.
이는 해당 문제를 완전 탐색으로 접근할 수 있다는 것을 의미한다.
그래서 2개의 수레가 움직일 때, 발생할 수 있는 모든 경우의 수를 따져보았다.
모든 경우의 수를 판단하는 법
두 수레의 출발점을 기준으로, 발생할 수 있는 모든 경우의 수를 시뮬레이션하는 방법은?
바로 백트래킹을 이용하는 것이다.
백트래킹을 이용하면, 발생할 수 있는 모든 경우의 수를 시뮬레이션할 수 있다.
두 수레는 모두 상하좌우로 움직일 수 있으므로,
턴에 발생할 수 있는 모든 경우의 수는 (상하좌우) x (상하좌우) = 16가지이다.
이 중에서 각 경우의 수로 움직였을 때, 가능한 경우에만 다음 턴을 이어나간다.
그렇게 다음턴에도 또 16가지의 경우의 수가 있을 것이고.. 이렇게 반복될 것이다.
이제 우리가 핵심적으로 알아야 할 것은 불가능한 경우가 어떤 것이 있는지이다.
모든 불가능한 경우
1. 기본적인 탐색(BFS, DFS) 규칙
기본적인 BFS 규칙을 검사한다.
두 수레 중 하나라도, 벽(5)으로 이동했거나, 이미 방문했던 위치로 이동했거나,
범위 밖으로 벗어났다면 불가능한 이동인 것이다.
2. 두 수레가 동시에 같은 위치로 이동할 때
두 수레가 이동한 곳의 좌표가 동일한 좌표라면, 그 위치는 이동이 불가능한 곳이다.
이를 항상 체크해줘야 한다.
3. 두 수레의 위치가 스위치 됐을 때
만약 A, B 수레의 위치가 뒤바뀐 위치라면 이동이 불가능하다.
실수하기 쉬운 부분
자신의 도착점에 들어온 수레는 더 이상 움직일 수 없다.
이 부분을 간과해서 틀리기 쉬운데, 자신의 도착점에 들어온 수레는 더 이상 움직일 수 없다.
이를 항상 체크해줘야 한다.
그렇지 않으면 도착한 것을 중복된 움직임으로 착각하고, 불가능으로 판단한다.
자세한 것은 코드로 보는 것이 훨씬 빠르게 때문에 코드에 주석으로 달아두겠다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <queue>
#define MAX 999999
using namespace std;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
bool visited[4][4][2] = {false};
bool redEnd,blueEnd;
int map[4][4] = {0};
int width,height;
struct Point{
int x,y;
};
// 해당 방향으로 움직임 반환
Point getNext(int x, int y, int dir){
int nx = x + dx[dir];
int ny = y + dy[dir];
return {nx,ny};
}
bool isPossible(Point cntRed, Point red,
Point cntBlue, Point blue){
// 기본 탐색 규칙
if(red.x < 0 || red.y < 0 || red.x >= height || red.y >= width
|| blue.x < 0 || blue.y < 0 || blue.x >= height || blue.y >= width
|| map[red.x][red.y] == 5 || map[blue.x][blue.y] == 5) return false;
// 두 수레 스위치 체크
if((cntRed.x == blue.x && cntRed.y == blue.y)
&& (cntBlue.x == red.x && cntBlue.y == red.y)) return false;
// 도착지점에 도착하지도 않고 중복방문이라면 false
if((!redEnd && visited[red.x][red.y][0])
|| (!blueEnd && visited[blue.x][blue.y][1])) return false;
// 두 수레가 동일한 지점에 위치시
if(red.x == blue.x && red.y == blue.y) return false;
return true;
}
// 백트래킹
int backtracking(Point red, Point blue, int result){
// 두 수레가 모두 도착 시 result 반환
if(redEnd && blueEnd) return result;
int answer = MAX;
// 2중 for문으로 16가지 경우의 수
for(int i = 0; i < 4; i++){
for(int j = 0; j < 4; j++){
// 도착지점에 도착한 경우엔 움직이지 않음
Point nRed = (!redEnd) ? getNext(red.x,red.y,i) : red;
Point nBlue = (!blueEnd) ? getNext(blue.x,blue.y,j) : blue;
// 불가능한 경우 conitnue
if(!isPossible(red,nRed,blue,nBlue)) continue;
visited[nRed.x][nRed.y][0] = true;
visited[nBlue.x][nBlue.y][1] = true;
if(map[nRed.x][nRed.y] == 3) redEnd = true;
if(map[nBlue.x][nBlue.y] == 4) blueEnd = true;
// 가장 적게 걸리는 턴 수
answer = min(answer,backtracking(nRed,nBlue,result+1));
// 방문 기록 및 도착 기록 초기화
redEnd = false;
blueEnd = false;
visited[nRed.x][nRed.y][0] = false;
visited[nBlue.x][nBlue.y][1] = false;
}
}
return answer;
}
int solution(vector<vector<int>> maze) {
Point cntRed,cntBlue;
height = maze.size();
width = maze[0].size();
for(int i = 0; i < maze.size(); i++){
for(int j = 0; j < maze[i].size(); j++){
map[i][j] = maze[i][j];
// 각 수레의 시작위치 초기화
if(maze[i][j] == 1) cntRed = {i,j};
else if(maze[i][j] == 2) cntBlue = {i,j};
}
}
// 시작 위치 방문 처리 (0은 빨간 수레, 1은 파란 수레)
visited[cntRed.x][cntRed.y][0] = true;
visited[cntBlue.x][cntBlue.y][1] = true;
int answer = backtracking(cntRed,cntBlue,0);
return (answer == MAX)? 0 : answer;
return answer;
}
Java 구현 코드
↓
import java.util.*;
class Solution {
private static class Point{
int x,y;
Point(int x,int y){
this.x = x;
this.y = y;
}
}
private static final int MAX = 999999;
public int[][] map;
private boolean redEnd, blueEnd;
private int[] dx = {-1,1,0,0};
private int[] dy = {0,0,-1,1};
private boolean[][][] visited;
public int solution(int[][] maze) {
Point cntRed = null;
Point cntBlue = null;
map = new int[maze.length][maze[0].length];
visited = new boolean[maze.length][maze[0].length][2];
for(int i = 0; i < maze.length; i++){
for(int j = 0; j < maze[i].length; j++){
map[i][j] = maze[i][j];
// 각 수레의 시작위치 초기화
if(maze[i][j] == 1) cntRed = new Point(i,j);
else if(maze[i][j] == 2) cntBlue = new Point(i,j);
}
}
// 시작 위치 방문 처리 (0은 빨간 수레, 1은 파란 수레)
visited[cntRed.x][cntRed.y][0] = true;
visited[cntBlue.x][cntBlue.y][1] = true;
int answer = backtracking(cntRed,cntBlue,0);
return (answer == MAX)? 0 : answer;
}
// 해당 방향으로 움직임 반환
private Point getNext(int x, int y, int dir){
int nx = x + dx[dir];
int ny = y + dy[dir];
return new Point(nx,ny);
}
// 해당 방향으로 움직이는 것이 가능한지 판단
// (현재 빨간 수레 , 다음 빨간 수레, 현재 파란 수레, 다음 파란 수레)
private boolean isPossible(Point cntRed, Point red,
Point cntBlue, Point blue){
// 기본 탐색 규칙
if(red.x < 0 || red.y < 0 || red.x >= map.length || red.y >= map[0].length
|| blue.x < 0 || blue.y < 0 || blue.x >= map.length || blue.y >= map[0].length
|| map[red.x][red.y] == 5 || map[blue.x][blue.y] == 5) return false;
// 두 수레 스위치 체크
if((cntRed.x == blue.x && cntRed.y == blue.y)
&& (cntBlue.x == red.x && cntBlue.y == red.y)) return false;
// 도착지점에 도착하지도 않고 중복방문이라면 false
if((!redEnd && visited[red.x][red.y][0])
|| (!blueEnd && visited[blue.x][blue.y][1])) return false;
// 두 수레가 동일한 지점에 위치시
if(red.x == blue.x && red.y == blue.y) return false;
return true;
}
// 백트래킹
private int backtracking(Point red, Point blue, int result){
// 두 수레가 모두 도착 시 result 반환
if(redEnd && blueEnd) return result;
int answer = MAX;
// 2중 for문으로 16가지 경우의 수
for(int i = 0; i < 4; i++){
for(int j = 0; j < 4; j++){
// 도착지점에 도착한 경우엔 움직이지 않음
Point nRed = (!redEnd) ? getNext(red.x,red.y,i) : red;
Point nBlue = (!blueEnd) ? getNext(blue.x,blue.y,j) : blue;
// 불가능한 경우 conitnue
if(!isPossible(red,nRed,blue,nBlue)) continue;
visited[nRed.x][nRed.y][0] = true;
visited[nBlue.x][nBlue.y][1] = true;
if(map[nRed.x][nRed.y] == 3) redEnd = true;
if(map[nBlue.x][nBlue.y] == 4) blueEnd = true;
// 가장 적게 걸리는 턴 수
answer = Math.min(answer,backtracking(nRed,nBlue,result+1));
// 방문 기록 및 도착 기록 초기화
redEnd = false;
blueEnd = false;
visited[nRed.x][nRed.y][0] = false;
visited[nBlue.x][nBlue.y][1] = false;
}
}
return answer;
}
}
시행착오
다양한 예외를 고려하지 못한 부분이 문제였던 것 같다.
복잡한 구현문제인걸 알고, 귀찮다 보니 쉽게 갈려다 보니 오히려 더 쉽게 안 풀렸는 듯..
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me