[프로그래머스] PCCP 기출 2 | 석유 시추

아래 프로그래머스 로고를 클릭하면 해당 문제로 이동합니다 😀

풀이과정

---

문제를 보자마자 일단 BFS를 생각하긴 했는데 알고리즘 안한지 너무 오래 되어서 구현하는데 살짝 애를 먹었다 ...

1. 일단 방문 여부를 판단하기위해 visited라는 2차원 배열을 land 크기와 동일하게 만들어줬다.

2. 이동 방향을 정해야하기 때문에 directions에 (-1, 0), (0, -1), (1, 0), (0, 1)을 넣어줬다. 앞뒤양옆으로 한칸씩 이동하는 경우를 넣어줬다.

3. 석유는 각 열마다 시추하므로 oil_sizes는 land의 열의 개수와 동일하게 만들어준다.

자자 이제 잘 생각해야한다 나도 문제 풀려고 생각하다가 자꾸 꼬여서 적는다 ... 후하

4. 이제 BFS를 진행할건데 나는 check_oil_size(x, y)라고 이름을 지었다.

5. deque를 사용해서 방문 지점인 [x, y]를 넣어준다. 그리고 [x, y]를 방문했으니까 visited[x][y]를 True로 바꿔주자.

6. 방문하면서 cnt라는 변수를 계속 늘릴거다. 석유가 있는 부분의 크기를 의미하게 될거다. 방문하면서 석유가 있는 칸이라면 1씩 증가하게 해줄거다.

7. row_oil_here 이라는 set을 선언했는데 이거는 방문한 열의 번호를 넣어줬다. 혹시라도 중복되는 경우를 방지하기 위해 set으로 만들어줬다.

자자 이제 진짜 BFS 알고리즘을 짜보자..

8. while문을 이용해서 queue를 확인해볼거다.
   queue.popleft()를 이용해서 왼쪽에서 요소를 꺼내오고, 그걸 현재 위치로 잡아준다.

9. 그리고 현재 위치를 기준으로 for문을 통해 directions 안의 요소들을 더해서 좌표를 이동한다.

10. 이동한 좌표가 land 크기를 벗어나지 않고, land에서 1을 가지고 있으며, 방문하지 않았다면 !
    이동한 좌표를 queue에 append 시키고, visited를 True로 변경해주고, cnt에 1을 더해주자.

11. 이렇게 while문을 처리하고서, 각 열마다 시추했을 때 석유 크기를 oil_sizes에 저장해주면 된다.

이렇게 적어놓고 생각하면 쉬운데 왜 머리가 안돌아가는걸까 싶네요 ?

12. 그러면 land를 방문하면서 land의 해당 좌표가 1이고 visited가 False라면 check_oil_size(해당 좌표)를 호출하면 되겠네요

13. 마지막으로, oil_sizes에서 최대값을 answer에 저장하고 return해주자

셀프 피드백 : 변수명을 깔끔하게 짓자 제발.. 코드가 지저분하다 ..

코드

---

from collections import deque

def solution(land):
    answer = 0
    rows, cols = len(land), len(land[0])

    visited = [[False] * cols for _ in range(rows)]
    direction = [(-1, 0), (0, -1), (1, 0), (0, 1)]

    oil_sizes = [0] * cols

    def check_oil_size(x, y):
      queue = deque()
      queue.append([x, y])
      visited[x][y] = True

      cnt = 1

      row_oil_here = {y}

      while queue:
        current_x, current_y = queue.popleft()
        for direction_x, direction_y in direction:
          move_x, move_y = current_x + direction_x, current_y + direction_y
          if 0 <= move_x < rows and 0 <= move_y < cols:
            if land[move_x][move_y] == 1 and not visited[move_x][move_y]:
              queue.append([move_x, move_y])
              visited[move_x][move_y] = True
              cnt += 1
              row_oil_here.add(move_y)
      
      for i in row_oil_here:
        oil_sizes[i] += cnt
                  
    for i in range(rows):
        for j in range(cols):
          if land[i][j] == 1 and not visited[i][j]:
            check_oil_size(i, j)
      
    answer = max(oil_sizes)
    return answer

결과

---