[파이썬]PCCP 기출문제 2번/ 석유 시추

https://school.programmers.co.kr/learn/courses/30/lessons/250136?language=python3

프로그래머스

---

bfs문제

1. y,x 축으로 한칸씩 이동하며, 석유 덩어리들을 묶어준다.
2. 덩어리 크기를 세어주고, 딕셔너리에 1번덩어리 7칸, 2번덩어리 8칸 매핑 해준다 ex) {1: 7, 2: 8, 3: 2}

3. 시추관을 꽂으면서 어느 석유덩어리에 꽂았는지 확인하고, 덩어리에 맞는 크기를 딕셔너리에서 가져와 더해준다.
4. 그중 가장 큰 x축의 값을 반환하면 끝!

 

def solution(land):
    answer = 0
    visited = [[0]* len(land[0]) for _ in range(len(land))]; # 방문배열
    
    # bfs
    def bfs(st):
        q = [];
        q.append(st);
        markCnt = 1;
        dy = [-1,1,0,0]
        dx = [0,0,-1,1]
        nMark = st[2];
        
        while q:
            nowy, nowx, nowMark = q.pop(0);
            for i in range(4):
                directy = dy[i] + nowy;
                directx = dx[i] + nowx;
                
                if 0 <= directy < len(land) and 0 <= directx < len(land[0]):
                    if visited[directy][directx] == 0 and land[directy][directx] == 1:
                        visited[directy][directx] = nowMark;
                        markCnt += 1;
                        q.append((directy, directx, nowMark))
                        
        markDic[nMark] = markCnt; # {1: 7, 2: 8} 이렇게 map 형식으로 해서 만든뒤, 시추 꽂을때 확인
    
    marked = 0;
    markDic = {};
    for y in range(len(land)):
        for x in range(len(land[y])):
            if visited[y][x] == 0 and land[y][x] == 1:
                marked += 1;
                visited[y][x] = marked;
                bfs((y, x, marked));
    
    for x in range(len(visited[0])):
        dig = [];
        for y in range(len(visited)):
            if visited[y][x] not in dig and visited[y][x] != 0:
                dig.append(visited[y][x]);
        
        ans = 0;
        for i in range(len(dig)):
            ans += markDic.get(dig[i])
        answer = max(ans, answer);
    return answer