2차원 맵에서 영역 구하기 (col-DFS)

                                    💡 두 가지 방법

1. 다 아는 상태에서 탐색
-- 모두 탐색 후 영역을 나눠둔다.
-- 영역이 나눠질 때 좌표쌍을 저장해둠
-- col 좌표별로 전체 석유를 계산하면된다.

2. 매번 탐색하기
-- col별로 탐색을 시작
-- 1을 만나면 DFS 시전
-- 0을 만나면 무시하고 내려간다.
-- 반복해서 최종 결과값 계산

                                    💡 DFS로 빠르게 탐색

석유 카운트 - max로 계속 갱신

1. col별로 탐색을 시작한다.
-- for i in range(col)

2. 0을 만나면 내려간다
-- row++

3. 1을 만나면 DFS 시작
-- visited
-- stack

⚠️ DFS의 0과 시추시의 0을 구분할 것

                                    def solution(land):
    move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    answer = -1
    totalCol = len(land[0])
    totalRow = len(land)

    # crt = col
    for i in range(totalCol):

        # start
        now_x, now_y = 0, i
        visited = [[0 for y in range(totalCol)] for x in range(totalRow)]
        col_max = 0

        while now_x < totalRow:
            # chekc one or zero
            if visited[now_x][now_y] == 1:
                now_x += 1
                continue
            visited[now_x][now_y] = 1

            if land[now_x][now_y] == 0:
                now_x += 1
                continue

            # dfs start when one
            position = [(now_x, now_y)]
            while position:
                cx, cy = position.pop()
                col_max += 1

                for i in range(4):
                    nx, ny = cx + move[i][0], cy + move[i][1]

                    if nx < 0 or ny < 0 or nx >= totalRow or ny >= totalCol:
                        continue

                    if visited[nx][ny] == 1 or land[nx][ny] == 0:
                        continue

                    position.append((nx, ny))
                    visited[nx][ny] = 1
            now_x += 1
        answer = max(answer, col_max)

    return answer

                                    ✏️ 시간 복잡도 분석

1. n = 500, m = 500
최대 250,000번의 탐색이 매 col마다 이뤄진다.
500 * 250,000 = 최대 125,000,000의 탐색

1억번의 탐색 -> 탐색이 너무 많다.

                                    💡 new Idea

1. 가장 첫 위치 (0, 0)에서 탐색을 시작하여 모든 석유 위치를 indexing한다.

2. list, set등을 이용하여 석유 영역을 분리해 둔다.
-- 총 석유의 수는 len으로 구하면 된다.

3. col i에 대한 전체 석유 수를 구하려면 아래 절차를 따른다.
-- a. 모든 list를 탐색하여 col i에 해당하는 좌표가 있는지 확인한다.
-- b. 있다면, 해당 list의 len을 구한다.
-- c. 모든 col i에 대해 반복한다.

                                    def solution(land):
    move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    answer = -1
    totalCol = len(land[0])
    totalRow = len(land)

    oil_positions = [] # [[(x, y), (x, y) ...]]
    visited = [[0 for y in range(totalCol)] for x in range(totalRow)]

    for i in range(totalRow):
        for j in range(totalCol):
            if visited[i][j] == 1:
                continue

            if land[i][j] == 1:
                visited[i][j] = 1
                oils = [(i, j)]
                stack = [(i, j)]
                while stack:
                    x, y = stack.pop()

                    for s in range(4):
                        nx, ny = x + move[s][0], y + move[s][1]

                        if nx < 0 or ny < 0 or nx >= totalRow or ny >= totalCol:
                            continue
                        if land[nx][ny] == 0 or visited[nx][ny] == 1:
                            continue

                        stack.append((nx , ny))
                        oils.append((nx, ny))
                        visited[nx][ny] = 1

                oil_positions.append(oils)

    print(oil_positions)
    for i in range(totalCol): # 상수 x
        col_max = 0
        for position in oil_positions: # n
            is_find = False
            for ps in position:
                if i == ps[1]:
                    is_find = True
                    break
            if is_find:
                col_max += len(position)

        answer = max(answer, col_max)

    return answer

                                    ✒️ 시간 복잡도
- n,m = 500

1. 처음 update 하는 for문 -> 500 * 500 = 250,000
2. dfs -> 1번에 포함됨
3. col을 체크하는 곳 -> i는 최대 500번, positions의 길이는 최대 500
이역시 500 * 500 = 250,000으로 분석된다.

❌ 그럼 총 500,000번의 연산이 기대되는 것으로 보이는데.. 화실히 연산 횟수가 줄어들었다.
👉 영역이 모두 1인 경우를 생각하자 -> [[x, y], [x1,y1], [x2,y2]...] 이게 250,000개 존재함
totalCol이 500이므로 결국에는 1번 경우와 똑같이 500 * 250,000번의 탐색이 이루어진다...!

                                    🔑 마지막 for문을 수정하는 것이 핵심 목표

✅ oil_positions만 순회한다.
✅ col_oil = [0] * totalCol로 선언
✅ oil_positions를 참고하여 col_oil을 갱신한다.

                                    def solution(land):
    move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    totalCol = len(land[0])
    totalRow = len(land)

    oil_positions = [] # [[(x, y), (x, y) ...]]
    visited = [[0 for y in range(totalCol)] for x in range(totalRow)]

    for i in range(totalRow):
        for j in range(totalCol):
            if visited[i][j] == 1:
                continue

            if land[i][j] == 1:
                visited[i][j] = 1
                oils = [(i, j)]
                stack = [(i, j)]
                while stack:
                    x, y = stack.pop()

                    for s in range(4):
                        nx, ny = x + move[s][0], y + move[s][1]

                        if nx < 0 or ny < 0 or nx >= totalRow or ny >= totalCol:
                            continue
                        if land[nx][ny] == 0 or visited[nx][ny] == 1:
                            continue

                        stack.append((nx , ny))
                        oils.append((nx, ny))
                        visited[nx][ny] = 1

                oil_positions.append(oils)

    col_oil = [0] * totalCol
    for position in oil_positions: # n
        visited = [0] * totalCol
        for ps in position:
            col = ps[1]
            if visited[col] == 1:
                continue
            col_oil[col] += len(position)
            visited[col] = 1

    return max(col_oil)