[Programmers] 보행자 천국

문제

 

2017 카카오코드 예선 > 보행자 천국

코딩테스트 연습 - 보행자 천국

 

 

아이디어

 

이번 문제는 DFS/BFS를 이용하여 풀어야 되는 것처럼 보이지만 DP를 이용하여 풀어야만 하는 문제입니다.

 

DP를 활용하는 방법은 간단합니다.

 

city_map배열을 순회하면서 현재 위치에서 다음 위치(오른쪽, 아래)를 이동하는 경우를 생각하거나 또는 이전 위치(왼쪽, 위)에서 현재 위치로 오게 하는 경우를 생각하면 됩니다.

 

저 같은 경우는 현재 위치에서 다음 위치로 이동하는 경우를 활용하여 풀었습니다.

 

DP를 이용한 풀이법도 다양하게 존재하는데 과반수 이상의 풀이는 3차원 배열을 생성하여 방향을 생각하며 저장하는 경우인 것 같지만 저 같은 경우는 2차원 배열을 사용하고 지나온 길을 되돌아가서 탐색하는 방법을 사용해봤습니다.

 

아이디어를 정리하면 다음과 같습니다.

 

1. city_map 인덱스를 탐색

2. 배열 값이 0일 경우는 현재까지 올 수 있는 경우를 배열 오른쪽과 아래쪽에 더하기

3. 배열 값이 2일 경우는 배열 값이 0이 나올때까지 왼쪽으로 되돌아가서 찾은 값을 오른쪽에 더하기, 배열 값이 0이 나올 때까지 위쪽으로 되돌아가서 아래쪽에 더하기

4. 모든 인덱스를 탐색할 때까지 1~3을 반복

 

 

구현 코드 (Java)

 

class Solution {
    public int solution(int m, int n, int[][] cityMap) {
        int array[][] = new int[m][n]; // 지나갈 수 있는 길의 개수 배열
        array[0][0] = 1;
        
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(cityMap[i][j] == 0) { // 자유롭게 지나가는 경우
                    if(i+1 < m) {
                        array[i+1][j] = (array[i+1][j] + array[i][j])%20170805; // 아래 쪽 길에 개수 더하기
                    }
                    
                    if(j+1 < n) {
                        array[i][j+1] = (array[i][j+1] + array[i][j])%20170805; // 오른 쪽 길에 개수 더하기
                    }
                } else if(cityMap[i][j] == 2) { // 좌회전, 우회전 방지 일 경우
                	if(i+1 < m) {
                		int targeti = i-1;
                		while(targeti >= 0) { // 자유롭게 지나가는 경우가 나올 떄 까지 일직선으로 되돌아가기
                			if(cityMap[targeti][j] == 0) {
                				break;
                			} else if(cityMap[targeti][j] == 1) {
                				targeti = -1;
                				break;
                			} else {
                				targeti--;
                			}
                		}
                		
                		if(targeti >= 0) {
                			array[i+1][j] = (array[i+1][j] + array[targeti][j])%20170805; // 아래 쪽 길에 개수 더하기
                		}
                	}
                    
                    if(j+1 < n) {
                    	int targetj = j-1;
                    	while(targetj >= 0) { // 자유롭게 지나가는 경우가 나올 때 까지 일직선으로 되돌아가기
                    		if(cityMap[i][targetj] == 0) {
                    			break;
                    		} else if(cityMap[i][targetj] == 1) {
                    			targetj = -1;
                    			break;
                    		} else {
                    			targetj--;
                    		}
                    	}
                    	
                    	if(targetj >= 0) {
                    		array[i][j+1] = (array[i][j+1] + array[i][targetj])%20170805; // 오른 쪽 길에 개수 더하기
                    	}
                    }
                }
            }
        }
        
        return array[m-1][n-1]%20170805;
    }
}

 

 

읽어주셔서 감사합니다.