방향 바꾸기 [그래프 문제] 풀이

문제:

현수에게 n * m 크기의 격자판으로 된 지도정보가 주어집니다. 지도의 각 격자에는 1, 2, 3, 4의 값이 있는데
1 : 오른쪽의 인접한 격자로 이동을 의미합니다.
2 : 왼쪽의 인접한 격자로 이동을 의미합니다.

3 : 아래로 인접한 격자로 이동을 의미합니다.
4 : 위로 인접한 격자로 이동을 의미합니다.
현수는 격자에 표현된 방향지시대로 0행 0열(격자의 왼쪽 가장 위) 지점에서 n-1행 m-1열 (격자의 오른쪽 가장 아래 지점)으로 이동하려고 합니다.
매개변수 board에 지도정보가 주어지면 현수가 (0, 0) 지점에서 (n-1, m-1)지점까지 가기 위 해서 방향을 바꾸어야 하는 최소 격자의 개수를 반환하는 프로그램을 작성하세요.
한 격자의 방향은 현수가 원하는 방향으로 오직 한 번만 바꿀 수 있습니다.

 

입력:

[[3, 1, 3],

[1, 4, 2],

[4, 2, 3]]

 

정답: 1

 

 

풀이:

1. 격자판 값에 따라 방향값을 담는 배열 세팅 (0번째는 안씀 1~4 값만 들어있기때문)

int[] dy= {0,0,0,1,-1};
int[] dx= {0,1,-1,0,0};

 

2. 다익스트라 알고리즘 사용. 가중치는 방향을 바꾼 횟수임.

다익스트라를 사용하기 때문에 가중치 낮은 순서대로 뽑아내기 위해 우선순위 큐 사용하며 

배열형태를 넣을것이다. int[] { 좌표1,좌표2, 가중치 }

 

3. 가중치는

격자판에 적힌 방향 정보 vs 반복문으로 네가지 방향으로 뽑은정보

를 비교해 같으면 격자판에 적힌대로 이동하는 것이니 가중치는 0 , 반대의 경우 현수가 방향을 임의적으로 바꿨다고

판단해 가중치 + 1 한 정보를 다익스트라 최소비용 비교에 사용될 int[][] dis 배열에 저장.

 

전체코드

public int solution(int[][] board) {
    int[] dy= {0,0,0,1,-1};
    int[] dx= {0,1,-1,0,0};
    int n = board.length;
    int m = board[0].length;
    int[][] dis = new int[n][m];
    for(int[] d : dis)Arrays.fill(d,Integer.MAX_VALUE);
    dis[0][0]=0;// 시작지점 초기화
    PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->(a[2]-b[2]));
    pq.offer(new int[]{0,0,0}); 
    while (!pq.isEmpty()){
        int[] x = pq.poll();
        int nowCost = x[2];
        int d = board[x[0]][x[1]]; // 격자판 방향정보
        if(x[2] > dis[x[0]][x[1]]) continue;
        for(int i=1; i<=4; i++){
            int ny = x[0] + dy[i];
            int nx = x[1] + dx[i];
            if(ny<0 || ny >= n || nx<0 || nx>=m) continue;
            // 격자판에 적힌 방향정보와 반복문 4방향 비교 후 격자판과 같은 방향이면 가중치는 0
            int cost = d == i ? 0 : 1; 
            if(dis[ny][nx] > nowCost + cost){
                dis[ny][nx] = nowCost + cost;
                pq.offer(new int[] {ny,nx,nowCost + cost});
            }
        }
    }

     return dis[n-1][m-1];
}

 

 

 

-출처 : 인프런 자바 코딩테스트 - it 대기업 유제 [김태원]