[프로그래머스][BFS] 석유 시추

석유 시추

프로그래머스

 

 

• 첫 풀이- 시간초과
  • 앞에서 확인한 석유그룹을 다른위치에서 방문할때마다 또 체크하니까 시간초과

from collections import deque

def solution(land):
    n=len(land)
    m=len(land[0])
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    
    def bfs(i,j,n,m):
        queue=deque()
        visited[i][j]=True
        queue.append((i,j))
        tmp=0
        
        while queue:
            x,y=queue.popleft()
            tmp+=1
            
            for k in range(4):
                nx=x+dx[k]
                ny=y+dy[k]
                
                if nx<0 or nx>=n or ny<0 or ny>=m:
                    continue
                if visited[nx][ny]==True:
                    continue
                if land[nx][ny]==0:
                    continue
                visited[nx][ny]=True
                queue.append((nx,ny))
        
        return tmp
                
    answer=[]
    for j in range(m):
        tmp=0
        visited=[[False for _ in range(m)] for _ in range(n)]
        for i in range(n):
            if land[i][j]==0:
                continue
            if visited[i][j]==True:
                continue
            tmp+=bfs(i,j,n,m)
        
        answer.append(tmp)
        
    return max(answer)

 

 

• 풀이
  • 방문한곳 석유 그룹에 같은 값 넣고 석유 그룹 ID 붙이기
    • 빠르게 하는 방법
    • 방문한 좌표를 따로 저장해두고 그걸 돌면서 표시하기
  • 수직으로 하나의 열을 확인할 때
    • 이전 행에서 더한 석유그룹 값을 다시 더하지 않도록
    • 방문한 석유그룹id SET에 보관해두고 확인

from collections import deque

def solution(land):
    n = len(land)
    m = len(land[0])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    oil = [[-1 for _ in range(m)] for _ in range(n)]
    oil_id = [[-1 for _ in range(m)] for _ in range(n)]
    visited = [[False for _ in range(m)] for _ in range(n)]
    current_num = 0

    def bfs(i, j, num):
        queue = deque()
        queue.append((i, j))
        visited[i][j] = True
        tmp = 0
        area = []

        while queue:
            x, y = queue.popleft()
            tmp += 1
            area.append((x, y))

            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]

                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    continue
                if visited[nx][ny]:
                    continue
                if land[nx][ny] == 0:
                    continue

                visited[nx][ny] = True
                queue.append((nx, ny))

        for x, y in area:
            oil[x][y] = tmp
            oil_id[x][y] = num

    for i in range(n):
        for j in range(m):
            if land[i][j] == 0:
                continue
            if oil[i][j] != -1:
                continue
            bfs(i, j, current_num)
            current_num += 1

    answer = []
    for j in range(m):
        tmp = 0
        num_set = set()
        for i in range(n):
            if oil[i][j] == -1:
                continue
            if oil_id[i][j] in num_set:
                continue
            tmp += oil[i][j]
            num_set.add(oil_id[i][j])
        answer.append(tmp)

    return max(answer)