코딩도장

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

석유가 있는곳은 1인 2차원 좌표가 주어지고, 위에서 아래로 파면서 한번에 석유를 가장 많이 얻을수 있는 열을 찾는 문제

bfs로 풀었더니 3번 4번 시간

from queue import Queue
def solution(land):
    answer = 0
    mx,my = len(land[0]), len(land)
    visited = [[False for _ in range(mx)] for _ in range(my)]
    direction = [[0,1],[-1,0],[0,-1],[1,0]]
    csum = [0 for _ in range(mx)]
    def bfs(r,c):
        queue = Queue()
        queue.put([r,c])
        visited[r][c]  = True
        cset = {c}
        cnt = 1
        while queue.empty() != True :
            r,c = queue.get()
            for dr, dc in direction:
                mr, mc = r+dr, c+dc
                if mr>=0 and mc>=0 and mr<my and mc<mx and land[mr][mc]==1 and visited[mr][mc] == False:
                    queue.put([mr,mc])
                    visited[mr][mc]  = True
                    cnt += 1
                    cset.add(mc)
        for v in cset:
            csum[v] += cnt
    
    for r, lst in enumerate(land):
        for c, v in enumerate(lst):
            if v==1 and visited[r][c]==False:
                bfs(r,c)
    answer = max(csum)
    return answer
#9
a = [[0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1, 1]]
print(solution(a))

이분은 비슷한데 bfs부분을 그냥 for문 밑에 달아 버렸음 심지어 이분은 queue도 안쓰고 그냥 리스트로 했는데 시간오버 안생김 

def solution(land):
    n, m = len(land), len(land[0])
    visited = [[True]*m for _ in range(n)]
    delta = [(1,0),(-1,0),(0,1),(0,-1)]
    oil_cnt = [0]*m
    for i in range(n):
        for j in range(m):
            if land[i][j] and visited[i][j]:
                visited[i][j] = False
                s = [(i,j)]
                col = set()
                oil = 0
                while s:
                    x, y = s.pop()
                    col.add(y)
                    oil += 1
                    for dx, dy in delta:
                        X, Y = x+dx, y+dy
                        if 0<=X<n and 0<=Y<m and land[X][Y] and visited[X][Y]:
                            visited[X][Y] = False
                            s.append((X,Y))
                for y in col:
                    oil_cnt[y] += oil
    return max(oil_cnt)

음 그래서 나도 for문 밑에 달아 봤더니 안된다 ㅠ

힘들게 queue까지 선언까지했는데  list가 더 빠른가