문제 요약

• $n \times m$ 크기의 땅이 있을때 석유가 있는 땅을 1 그렇지 않은 땅을 0이라고 한다.
• 석유 시추를 할 때 가장 많은 석유를 시추하는 땅을 고른다

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

아이디어

• 석유 방에 각각 번호를 붙이고 그 번호의 개수를 따로 기록한다.
• 이후 집합을 이용하여 시추공간이 들어가는 곳에 어떤 방이 있는지 확인한 뒤, 미리 기록한 방의 크기를 더한다.
• 가장 큰 값을 리턴한다.

코드

from collections import deque
def solution(land):
    n, m = len(land), len(land[0])
    visited = [[-1] * m for _ in range(n)]
    space = {-1:0}

    def dfs(x, y, d):
        nonlocal land, visited
        q = deque([[x, y]])
        visited[x][y] = d

        dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
        cnt = 1
        while q:
            cx, cy = q.popleft()
            for i in range(4):
                nx, ny = cx + dx[i], cy + dy[i]
                if 0 <= nx < n and 0 <= ny < m and land[nx][ny] == 1 and visited[nx][ny] == -1:
                    q.append([nx, ny])
                    visited[nx][ny] = d
                    cnt += 1
        return cnt
    
    f = 0
    for i in range(n):
        for j in range(m):
            if visited[i][j] == -1 and land[i][j] == 1:
                space[f] = dfs(i, j, f)
                f += 1

    result = 0

    for i in list(zip(*visited)):
        temp = 0
        for j in set(i):
            temp += space[j]
        result = max(result, temp)
    return(result)

배운 것

• 풀이시간 : 35분
• 프로그래머스는 solve() 함수를 호출하여 그 함수에서 리턴한 결과가 테스트케이스와 맞으면 정답을 출력하는 방식이다.
• 이전까지는 다른 함수를 만들어서 변수의 scope를 고려하는것이 번거로웠는데 inner 함수를 만들 수 있다는 것을 생각해내지 못했었다.
• 중요한점은 inner함수에서 outer 함수의 변수를 가져오려면 global 키워드가 아닌 nonlocal을 사용해야 한다는 것