[BOJ] 1012 - 유기농 배추

사용 언어: Python3

문제

백준 1012

Flood Fill의 대표적인 문제이다.

내 풀이

첫 번째

T = int(input())

dx, dy = [0, -1, 0 ,1], [1, 0, -1, 0]

def bfs(field,x,y):
  # 구현을 어떻게 하지..

def process():
  M, N, K = map(int, input().split())
  cnt = 0

  # 배추밭
  field = [[0 for _ in range(M)] for _ in range(N)]

  # update field
  for _ in range(K):
    x, y = map(int, input().split()) # 배추가 심어진 위치
    field[x][y] = 1

  for i in range(N):
    for j in range(M):
      for k in range(4):
        bfs(field, i+dx[k], j+dy[k])

  # output
  print(cnt)
  

for _ in range(T):
  process()

• 풀이 실패..

두 번째

import sys
import sys
sys.setrecursionlimit(10000)

T = int(input())

dx, dy = [0,-1,0,1], [1,0,-1,0]

def bfs(field,ck,x,y):
  ck[x][y] = True
  for i in range(4):
    xx, yy = x+dx[i], y+dy[i]
    if field[xx][yy] == 1 and not ck[xx][yy]: # ✅ 조건 체크
      bfs(field,ck,xx,yy)

def process():
  M, N, K = map(int, input().split())

  field = [[0 for _ in range(M+2)] for _ in range(N+2)]
  ck = [[False for _ in range(M+2)] for _ in range(N+2)] # 방문했는지 체크

  for _ in range(K):
    x, y = map(int, input().split())
    field[y+1][x+1] = 1 # ✅ [y][x] 인덱스 주의!

  cnt = 0
  for i in range(1,N+1):
    for j in range(1,M+1):
      if field[i][j] == 1 and not ck[i][j]: # ✅ 조건 체크
        bfs(field,ck,i,j)
        cnt += 1
  print(cnt)

for _ in range(T):
  process()

• 전역변수를 사용하지 않고 풀어봤다.
• 문제에서 x를 가로, y를 세로 입력값으로 설정했기 때문에 2차원 배열의 인덱스로 가져갈 때는 field[y][x]와 같이 표현한다.

  배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50)
  배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다.
  

• bfs 호출할 때와, bfs 내부에서 bfs를 재귀호출 할 때 조건을 잘 체크하자!

다른 사람 풀이 - DFS

import sys
sys.setrecursionlimit(10000) # ✅ 재귀함수의 깊이를 제한 # 너무 깊어지면 런타임에러가 발생하기 때문

T = int(input())
field = [] # 전역변수
ck = [] # map에서 탐색한 부분은 탐색했다고 표시할 배열

dx, dy = [0,-1,0,1], [1,0,-1,0]

def dfs(x,y):
  global field, ck
  ck[x][y] = True
  for i in range(4):
    xx, yy = x+dx[i], y+dy[i] # xx, yy는 그 다음에 돌 점
    if field[xx][yy] == 0 or ck[xx][yy]:
      continue
    dfs(xx,yy)

def process():
  global field, ck
  M, N, K = map(int, input().split())
  # ✅ 네 테두리에 한 줄씩 추가해서 푸는 것을 추천
  field = [[0 for _ in range(M+2)] for _ in range(N+2)]
  ck = [[False for _ in range(M+2)] for _ in range(N+2)]
  
  for _ in range(K):
    x, y = map(int, input().split())
    field[y+1][x+1] = 1 # ✅ 네 테두리에 한 줄씩 추가했기 때문에 (0,0)으로 입력 받았다면 (1,1) 자리에 채워야 한다
  print(field)

  cnt = 0
  for i in range(1, N+1):
    for j in range(1, M+1):
      if field[i][j] == 0 or ck[i][j]: # 이미 방문했다면
        continue
      dfs(i,j) # 그 지점에서 순회
      cnt += 1
  print(cnt)

for _ in range(T):
  process()

• Flood Fill의 핵심은 1. 일단은 전체 탐색을 한 뒤 2. 탐색한 부분은 다시 탐색하지 않는 것이다.
• sys.setrecursionlimit(10000)를 통해 재귀함수 깊이를 제한해주지 않으면 런타임 에러가 발생하니 주의하자!

내 풀이 - 0526 추가

import sys
sys.setrecursionlimit(10**6) # 🚨 안하면 런타임에러 !!

def process():
    N, M, K = map(int, input().split())
    board = [[0] * M for _ in range(N)]
    visited = [[0] * M for _ in range(N)]
    for _ in range(K):
        x, y = map(int, input().split())
        board[x][y] = 1

    dx, dy = [0,-1,0,1],[1,0,-1,0]
    def DFS(x, y):
        visited[x][y] = 1
        for w in range(4):
            xx, yy = x+dx[w], y+dy[w]
            if xx<0 or xx>=N or yy<0 or yy>=M:
                continue
            if board[xx][yy] == 0 or visited[xx][yy]:
                continue
            visited[xx][yy] = 1
            DFS(xx, yy)

    cnt = 0
    for i in range(N):
        for j in range(M):
            if board[i][j] == 0 or visited[i][j]:
                continue
            cnt += 1
            DFS(i, j)
    print(cnt)


T = int(input())
for _ in range(T):
    process()

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기