[Leetcode] 1706. Where Will the Ball Fall

문제

 

https://leetcode.com/problems/where-will-the-ball-fall/

Where Will the Ball Fall - LeetCode

You have a 2-D grid of size m x n representing a box, and you have n balls. The box is open on the top and bottom sides.

Each cell in the box has a diagonal board spanning two corners of the cell that can redirect a ball to the right or to the left.

• A board that redirects the ball to the right spans the top-left corner to the bottom-right corner and is represented in the grid as 1.
• A board that redirects the ball to the left spans the top-right corner to the bottom-left corner and is represented in the grid as -1.

We drop one ball at the top of each column of the box. Each ball can get stuck in the box or fall out of the bottom. A ball gets stuck if it hits a "V" shaped pattern between two boards or if a board redirects the ball into either wall of the box.

Return an array answer of size n where answer[i] is the column that the ball falls out of at the bottom after dropping the ball from the ith column at the top, or -1 if the ball gets stuck in the box.

 

크기가 m * n인 grid 배열이 주어지고, n개의 공이 주어질 때 공의 마지막 위치를 구해서 반환해라.

• 공이 오른쪽 하단으로 내려갈 때는 grid가 1로 표시된다
• 공이 왼쪽 하단으로 내려갈 때는 grid가 -1로 표시된다

answer[i]는 공이 굴러가는 경로가 V 모양을 하고있거나, 배열 밖으로 나갈때에는 -1, 가장 끝까지 내려왔을 때는 현재 column의 위치를 입력한다

 

Example 1:

Input	Output
grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]	[1,-1,-1,-1,-1]
Explanation: This example is shown in the photo. Ball b0 is dropped at column 0 and falls out of the box at column 1. Ball b1 is dropped at column 1 and will get stuck in the box between column 2 and 3 and row 1. Ball b2 is dropped at column 2 and will get stuck on the box between column 2 and 3 and row 0. Ball b3 is dropped at column 3 and will get stuck on the box between column 2 and 3 and row 0. Ball b4 is dropped at column 4 and will get stuck on the box between column 2 and 3 and row 1.

 

Example 2:

Input	Output
grid = [[-1]]	[-1]
Explanation: The ball gets stuck against the left wall.

 

 

문제풀이 코드

class Solution:
    def findBall(self, grid: List[List[int]]) -> List[int]:
        N, M = len(grid), len(grid[0])
        result = [0] * M
        def dfs(x, y):
            if x >= N:
                return y
            if grid[x][y] == 1:
                if y + 1 >= M:
                    return -1
                if grid[x][y + 1] == -1:
                    return -1
                return dfs(x + 1, y + 1)
            if grid[x][y] == -1:
                if y - 1 < 0:
                    return -1
                if grid[x][y - 1] == 1:
                    return -1
                return dfs(x + 1, y - 1)
        for i in range(M):
            result[i] = dfs(0, i)
        return result

 

깊이 우선 탐색을 이용하여 문제 풀이

1. grid[x][y]가 1이면 오른쪽으로 이동하고 -1이면 왼쪽으로 이동

2. 현재 위치가 1(오른쪽으로이동)이고 grid[x][y+1]이 -1일 때 길이 막히기 때문에 -1을 반환

3. 마찬가지로 현재 위치가 -1(왼쪽으로이동)일 때 grid[x][y-1]이 1일 때 길이 막히기 때문에 -1을 반환

4. x의 크기가 N보다 크거나 같으면 현재 y를 반환한다.

5. 모든 공을 출발시켜서 해당 값을 받아서 결과를 반환한다.