호우동의 개발일지

Today :

article thumbnail

문제 링크
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;
    }
}

 


시행착오

다양한 예외를 고려하지 못한 부분이 문제였던 것 같다.
복잡한 구현문제인걸 알고, 귀찮다 보니 쉽게 갈려다 보니 오히려 더 쉽게 안 풀렸는 듯..

https://toss.me/howudong

 

howudong님에게 보내주세요

토스아이디로 안전하게 익명 송금하세요.

toss.me