[프로그래머스] PCCP 기출 2번 시추관 - 파이썬

https://school.programmers.co.kr/learn/courses/19344/lessons/242259

DFS나 BFS를 활용하는 문제였다.

1차 풀이

단순하게 세로축마다 DFS를 반복했고 정답은 나왔지만 당연하게 효율성 검사에서 모두 실패했다.

DFS를 전체에 대해 한번만하고 이것을 기록하여 활용하는 것이 효율성 검사 통과의 중점이라고 생각해서 코드를 수정했다.

2차 풀이

import sys
sys.setrecursionlimit(10**6)

def solution(land):
    answer = 0

    n = len(land)
    m = len(land[0]) # 1 ~ m까지
    print(n,m)

    def dfs(x,y,graph,visited,area,cnt):
        dx = [1,-1,0,0]
        dy = [0,0,1,-1]

        if graph[x][y]==1:
            visited[x][y] = cnt
            area.append([x,y])
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if 0<=nx<n and 0<=ny<m and graph[nx][ny]==1:
                    if not visited[nx][ny]:
                        dfs(nx,ny,graph,visited,area,cnt)

    visited = [[0 for _ in range(m)] for _ in range(n)]
    cnt=1
    # 0을 넣은 이유는 visited가 1부터 시작하기 때문에 인덱스를 맞추기 쉽게 하기 위함이다.
    area_list = [0] 
    for i in range(n):
        for j in range(m):
            if not visited[i][j] and land[i][j]==1:
                area = []
                dfs(i,j,land,visited,area,cnt)
                area_list.append(area)
                cnt+=1

    for i in range(m):
        temt_set = set()
        ans = 0
        for j in range(n):
            if visited[j][i]:
                temt_set.add(visited[j][i])

        for k in temt_set:
            ans+= len(area_list[k])
        if ans>answer:
            answer=ans

    return answer

문제 접근 방식은 다음 순서처럼 진행했다.

1. 전체에 대해 DFS를 실행하고, 영역마다 방문했을때 넣는 숫자를 다르게 하였다. (구역 나누기)

2. area_list 에 한번 DFS를 실행할때 방문하는 좌표들의 리스트를 하나의 원소로 담았다.

3. visited와 area_list 는 각각 아래와 같은 형태로 나온다.

visited 에서 1번 구역에 속한 좌표들은 area_list의 1번 인덱스에 해당하는 리스트에 담겨있으며 이 길이가 곧 영역의 넓이이므로 더해주면 된다.