(C#) 아이템 줍기

코딩테스트 연습 - 아이템 줍기 | 프로그래머스 스쿨

프로그래머스

 

입력된 사각형들로 지도를 만들고, 길을 찾는 문제

 

세 단계로 진행했다.

1. 입력된 사각형들로 지도 만들기

- 입력된 사각형의 내부를 모두 1로 채운다

2. 지도를 가공하기

- 만들어진 지도에서 내부의 1을 모두 0으로 바꾼다

3. 지도에서 길찾기

 

핵심 아이디어는 지도를 만들 때 원래 좌표에 2배를 해주는 것이다.

왼쪽은 2배를 하지 않은 지도이고, 오른쪽은 2배를 한 지도다.

왼쪽 지도에서 파란 칸에서 빨간 칸으로 이동하는 길을 찾을 때, 원래는 초록색 경로로 가야한다.

그런데 1이 서로 인접해있으므로 노란색 경로를 따라가게 된다.

좌표를 2배수를 해주면 이런 일을 방지할 수 있다.

 

코드

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int[,] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int answer = 0;
        int[,] coordinate = new int[102, 102];
        
        // 초기 지도
        for(var i = 0; i < rectangle.GetLength(0); i++){
            var min_x = rectangle[i, 0];
            var min_y = rectangle[i, 1];
            var max_x = rectangle[i, 2];
            var max_y = rectangle[i, 3];
            for(var m = min_x * 2; m <= max_x * 2; m++){
                for(var n = min_y * 2; n <= max_y * 2; n++){
                    coordinate[m, n] = 1;
                }
            }
        }
        
        int[,] temp = new int[102, 102];
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};
        // 지도 가공
        for(var i = 2; i < 101; i++){
            for(var j = 2; j < 101; j++){
                // 1
                bool flag = false;
                for(var x = 0; x < dx.Length; x++){
                    for(var y = 0; y < dy.Length; y++){
                        if(coordinate[i + dx[x], j + dy[y]] == 0){
                            flag = true;
                            break;
                        }
                    }
                    if(flag) break;
                }
                if(flag) {
                    temp[i, j] = coordinate[i, j];
                    continue;
                }
                temp[i, j] = 0;
            }
        }
        
        // 길찾기
        var _x = characterX * 2;
        var _y = characterY * 2;
        var queue = new Queue<(int x, int y, int distance)>();
        var visited = new List<(int x, int y)>();
        queue.Enqueue((_x, _y, 0));
        visited.Add((_x, _y));

        while(queue.Count != 0){
            var current = queue.Dequeue();
            if(current.x == 2*itemX && current.y == 2*itemY){
                return current.distance / 2;
            }
            for(var i = 0; i < dx.Length; i++){
                for(var j = 0; j < dy.Length; j++){
                    if(temp[current.x + dx[i], current.y + dy[i]] == 1 && !visited.Contains((current.x + dx[i], current.y + dy[i]))){
                        queue.Enqueue((current.x + dx[i], current.y + dy[i], current.distance + 1));
                        visited.Add((current.x + dx[i], current.y + dy[i]));
                    }
                }
            }
        }
        return answer;
    }
}

 

결과