[프로그래머스] Swift - 공 이동 시뮬레이션

https://school.programmers.co.kr/learn/courses/30/lessons/87391

프로그래머스

 

2023.11.09 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

문제 조건

• n x m 크기의 격자 존재 (2차원 배열)
• 특정 좌표에서 시작해서 queries에 담긴 이동을 전부 마치고 (x, y)에 도달하는 경우를 찾아서 해당 시작 좌표의 개수를 구해야 한다.
• 이동 중에 벽을 만나면 벽에 닿은 지점에서 멈추게 된다.

 

이동 후 마지막 좌표가 아닌 시작 좌표를 구해야 하는 문제입니다.

대신 도착 좌표인 x, y가 주어졌습니다.

 

제한 사항을 보면 n과 m의 크기가 최대 10^9 이기 때문에 배열을 전부 탐색하며 경우의 수를 찾는 것은 무조건 시간 초과가 발생할 것임을 예상할 수 있습니다.

 

우리가 가지고 있는 데이터는 도착지 좌표와 이동 경로입니다.

이걸 바탕으로 역추적하여 출발 지점을 찾는 방식을 사용해야 했습니다.

즉, queries 배열을 뒤집어서 역순으로 도착지부터 이동을 시키는 것입니다.

 

query에서는 위로 3칸 가라고 지시했다면 역방향으로 아래로 3칸 내리는 방식으로 도착지로부터 출발지를 유추합니다.

 

이 아이디어까지는 생각할 수 있었는데 더욱 구체적인 방법이 필요했습니다.

벽에 닿았을 경우, 배열 인덱스 범위를 넘어가는 경우에는 어떻게 이동시킬지가 이 문제의 핵심이었습니다.

링크에서 이러한 아이디어에 대한 구체적인 해설이 있어서 참고했습니다.

 

도착지부터 역순으로 출발지를 찾는 다는 기조는 여전히 같고 추가적으로 쿼리가 상하좌우로만 움직이기 때문에 가능한 출발지의 범위 또한 직사각형으로 유지된다는 아이디어가 추가되었습니다.

 

출발지가 가능한 범위를 좌표로 저장하고 (직사각형의 좌상단, 우하단 좌표) 이 좌표들을 이동시키면서 출발지의 범위를 구합니다.

마지막에는 이 직사각형의 넓이를 리턴하면 문제에서 요구하는 출발지의 개수를 충족시킬 수 있습니다.

 

직사각형의 크기 및 위치를 조정하는 과정에서 벽에 닿는 경우를 처리하는 것이 중요합니다.

	O	O
	O	O

 

현재 직사각형이 위와 같다면 (O로 표시한 영역)

이 상태에서 query가 행을 줄이는 방향으로 2칸이라면 이를 역으로 수행하여

	O	O
	O	O

 

행을 늘리는 방향으로 2칸 이동시키면 됩니다.

 

하지만 만약 초기 상태가

	O	O
	O	O

 

이렇게 이동 방향과 같은 벽에 닿아있다면 문제 조건에서 벽에 닿으면 이동을 멈춘다는 조건이 있기 때문에

 

	O	O
	O	O
	O	O
	O	O

 

이처럼 행을 늘리는 방향으로 2칸 전체적으로 이동하는 것이 아니라 2칸 범위가 증가하는 방식으로 직사각형의 크기가 조정됩니다.

왜냐하면 붉은색으로 표시한 위치에서도 위로 2칸 올렸을 때 도착지 범위로 도착이 가능하기 때문입니다.

 

 

정리하면 query가 이동하려는 방향의 벽에 이미 맞닿아 있다면 반대 방향으로 직사각형의 크기를 늘린다.

맞닿아 있지 않다면 직사각형 전체를 반대 방향으로 이동시킨다. (크기는 변하지 않고 위치만 변함)

 

 

마지막으로 범위 밖으로 직사각형이 나가버리는 경우를 방지해야 합니다.

 

만약, 쿼리 수행 후에 직사각형의 좌상단 좌표가 우하단 좌표를 넘어서게 되면 이는 출발지 범위 직사각형이 존재할 수 없는 경우기 때문에 곧바로 return 0을 수행하면 됩니다.

 

또한 직사각형을 이동시키다가 격자를 넘어서는 일이 발생할 수 있습니다.

예를 들어

	O	O
	O	O
	O	O

 

이 상태에서 아래로 2칸 내려가는 쿼리 차례가 온다면 우리는 역으로 위로 2칸 올려야합니다.

위의 상태에서 좌상단 좌표는 (0,1) 우하단은 (2, 2)인데 위로 2칸을 올리면

각각 (-2, 1), (0, 2)이 됩니다.

 

하지만 격자를 그렸을 때 실제로는

	O	O

 

이렇게 직사각형이 남아있어야 합니다.

즉 좌표가 각각 (0, 1), (0,2)가 되어야 한다는 것입니다.

따라서, 격자 범위를 넘어서게 되면 직사각형 좌표를 재조정하여 직사각형 크기 안에 들어오도록 설정해야 합니다.

코드로 표현하면 다음과 같습니다.

// x1, y1은 좌상단 좌표, x2, y2는 우하단 좌표
x1 = max(x1, 0)
y1 = max(y1, 0)
x2 = min(x2, n-1)
y2 = min(y2, m-1)

 

 

 

풀이

fileprivate func solution(_ n:Int, _ m:Int, _ x:Int, _ y:Int, _ queries:[[Int]]) -> Int64 {
    let queries = queries.reversed()
    // 직사각형의 좌상단 좌표
    var x1 = x
    var y1 = y
    // 직사각형의 우하단 좌표
    var x2 = x
    var y2 = y
    
    for query in queries {
        let direction = query[0]
        let distance = query[1]
        
        switch direction {
        case 0: // 좌
            if y1 == 0 {
                y2 += distance
            } else {
                y1 += distance
                y2 += distance
            }
        case 1: // 우
            if y2 == m-1 {
                y1 -= distance
            } else {
                y1 -= distance
                y2 -= distance
            }
        case 2: // 위
            if x1 == 0 {
                x2 += distance
            } else {
                x1 += distance
                x2 += distance
            }
        case 3: // 아래
            if x2 == n-1 {
                x1 -= distance
            } else {
                x1 -= distance
                x2 -= distance
            }
        default:
            break
        }
        
        if x1 >= n || y1 >= m || x2 < 0 || y2 < 0 {
            return 0
        }
        
        x1 = max(x1, 0)
        y1 = max(y1, 0)
        x2 = min(x2, n-1)
        y2 = min(y2, m-1)
    }
    
    let size = (x2-x1+1) * (y2-y1+1)
    
    return Int64(size)
}

 

1. queries를 reverse 시킵니다.
2. 직사각형의 범위를 구하기 위해 좌상단 좌표와 우하단 좌표를 담을 변수들을 선언합니다. (x1,y1, x2,y2)
3. queries를 순회하며 직사각형의 크기와 위치를 변경시킵니다.
   1. query의 방향과 반대 방향으로 이동시킵니다.
   2. 벽에 닿아있는 상태에서 해당 방향으로 query가 이동을 지시하면 직사각형의 크기를 늘립니다.
   3. 벽에 닿아있지 않거나 벽에 닿아있는 방향이 아닌 곳으로 이동을 지시하면 직사각형 전체의 위치를 이동시킵니다. (크기 변화 X)
4. 각 쿼리를 수행하고 직사각형이 유효한지 검사하여 아니라면 return 0을 수행합니다.
5. 직사각형이 격자를 일부 벗어난다면 다시 격자 안의 범위에 해당하는 직사각형의 좌표로 수정해줍니다.
6. 모든 쿼리를 수행하고 구해진 직사각형의 크기(넓이)를 구합니다.
7. 해당 크기를 리턴합니다.

 

 

 

마무리

막상 코드로 구현하고 나면 간단해 보이지만 쿼리를 역순으로 찾아야 한다는 아이디어 + 벽에 닿았을 때, 범위를 벗어났을 때 어떻게 직사각형의 위치와 크기를 조정할지에 대한 처리가 필요해서 난이도가 높았던 것 같습니다.

앞서 첨부한 프로그래머스 질문하기 탭 링크에서 친절하게 설명을 잘 해주고 계셔서 해당 글을 읽고 코드를 보면 이해가 더 쉬워질 것 같습니다..!