959. Regions Cut By Slashes

[zeikar]

Problem link

https://leetcode.com/problems/regions-cut-by-slashes/

Problem Summary

슬래시로 나뉜 영역의 개수를 세는 문제.

Solution

원본 그리드에서 개수를 세는건 꽤 복잡하다. 그래서 크기를 키운 3x3 그리드에서 영역의 개수를 셀 수 있다.

출처: 에디토리얼

시간복잡도는 O(n^2)

2x2 그리드로 풀기

나는 처음에 4x4로 풀었는데 잘 생각해보니 2x2로도 될 것 같다.
원본 그리드를 참고해서 / 이면 대각선으로 1,3분면을 이동 가능하게 하고 \이면 2,4분면을 이동 가능하게 만들면 2x2 그리드로도 풀 수 있다.

예시로

//
/

위 입력을 2x2 그리드로 확장하면

0101
1010
0100
1000

이 되는데, (0,2)에서는 원본 그리드에서 / 이므로 (1,1)로 대각선 이동이 가능하다고 볼 수 있다.

Source Code

class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        n = len(grid)
        m = n * 2
        grid2 = [[0] * m for _ in range(m)]

        for i in range(n):
            for j in range(n):
                if grid[i][j] == "/":
                    grid2[2*i][2*j+1] = 1
                    grid2[2*i+1][2*j] = 1
                elif grid[i][j] == "\\":
                    grid2[2*i][2*j] = 1
                    grid2[2*i+1][2*j+1] = 1

        def dfs(x, y):
            if x < 0 or x >= m or y < 0 or y >= m or grid2[x][y] == 1:
                return
            grid2[x][y] = 1

            dir = [[1, 0], [0, 1], [0, -1], [-1, 0]]
            if grid[x//2][y//2] == "/":
                dir += [[1, -1], [-1, 1]]
            elif grid[x//2][y//2] == "\\":
                dir += [[1, 1], [-1, -1]]

            for d in dir:
                dfs(x+d[0], y+d[1])

        ans = 0
        for i in range(m):
            for j in range(m):
                if grid2[i][j] == 0:
                    ans += 1
                    dfs(i, j)
        return ans