프로그래머스 석유 시추 파이썬

https://school.programmers.co.kr/learn/courses/30/lessons/250136

프로그래머스

 

from collections import deque,defaultdict

def solution(land):
    answer = 0
    num={}
    def bfs(y,x,gul):
        count=1
        re=[[y,x]]
        q=deque()
        q.append([y,x])
        visited[y][x]=gul
        dx=[0,0,-1,1]
        dy=[-1,1,0,0]
        while q:
            y,x=q.popleft()
            for i in range(4):
                new_x=x+dx[i]
                new_y=y+dy[i]
                if 0<=new_x<len(land[0]) and 0<=new_y<len(land) and visited[new_y][new_x]==0 and land[new_y][new_x]!=0:
                    visited[new_y][new_x]=gul
                    q.append([new_y,new_x])
                    count+=1
        num[gul]=count
    cnt=0
    gul=1
    visited=[[0]*len(land[0]) for _ in range(len(land))]
    for i in range(len(land)):
        for j in range(len(land[0])):
            if land[i][j]==1 and visited[i][j]==0:
                bfs(i,j,gul)
                gul+=1
        
    for j in range(len(land[0])):
        li=set()
        r=0
        for i in range(len(land)):
            if visited[i][j]!=0:
                li.add(visited[i][j])
        for k in li:
            r+=num[k]
        cnt=max(cnt,r)
    answer=cnt
    return answer

 

dfs/bfs를 공부하고 처음 풀어 봤던 문제. 

 

코딩 테스트에서는 좌표에 대한 내용이나 블럭, 섬, 연결된 경로 같은 내용이 나오면 dfs/bfs 부터 떠올리고 내용을 상상해본다.