[ BOJ / 파이썬 ] 1012 유기농 배추

 

/  첫 번째 제출  /

import sys
from collections import deque
input = sys.stdin.readline

T = int(input())

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

for t in range(T):
  # 초기화
  ## 가로, 세로, 배추 개수
  m, n, k = map(int, input().split())
  farm = [[0] * m for _ in range(n)]  
  visited = [[False] * m for _ in range(n)]  
  q = deque([])
  cabbageq = deque([])
  for i in range(k):
    y, x = map(int, input().split())
    farm[x][y] = 1

  worm = 0
  for x in range(n):
    for y in range(m):
      if farm[x][y] == 1 and not visited[x][y]:
        q.append((x, y))
        
        while q: 
          x, y = q.popleft()
          visited[x][y] = True 
          for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
              if farm[nx][ny] == 1 and not visited[nx][ny]:
                q.append((nx, ny))
                
        worm += 1
  
  print(worm)

: 시간 초과.

: 간만에 원 큐에 풀고, 답도 잘 떨어진다 했다! python 시간 초과, pypy3 혹시 몰라 했는데 얘도 메모리 초과.

: 값이 주어질 때부터 전체 맵 형식이 아니라 배추 위치를 하나 하나 주는 방식이어서 혹시나 했는데 역시 받을 때마다 체크해줘야했나보다! 다시 풀어봐야겠다.

 

 

/  2번째 제출  /

import sys
from collections import deque
input = sys.stdin.readline

T = int(input())

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

for t in range(T):
  # 초기화
  ## 가로, 세로, 배추 개수
  m, n, k = map(int, input().split())
  farm = [[0] * m for _ in range(n)]  
  visited = [[False] * m for _ in range(n)]  
  q = deque([])
  cabbageq = deque([])
  for i in range(k):
    y, x = map(int, input().split())
    farm[x][y] = 1
    cabbageq.append((x, y))

  worm = 0
  while cabbageq:
    x, y = cabbageq.popleft()
    if farm[x][y] == 1 and not visited[x][y]:
      q.append((x, y))
      
      while q: 
        x, y = q.popleft()
        visited[x][y] = True 
        for i in range(4):
          nx = x + dx[i]
          ny = y + dy[i]
          if 0 <= nx < n and 0 <= ny < m:
            if farm[nx][ny] == 1 and not visited[nx][ny]:
              q.append((nx, ny))
              
      worm += 1
  
  print(worm)

: 시간 초과

: 뭐지 ?! 의심되는 부분 바꿔줬더니 그래도 1-2%는 갔는데 그래도 터졌다. 사실 x, y가 50 이하라서 2중 for문해도 그렇게 크게 차이가 안 났을 것 같다고 생각된다.

: 그러면 배추 개수가 2500개로 max일 때 문제가 있다는 건가. 그럴리 없는데..? 너무 작잖아..

: 로직은 맞는 것 같은데 뭘까 진짜 ㅠ

 

 

/ 3번째 제출  /

import sys
from collections import deque
input = sys.stdin.readline

T = int(input())

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

for t in range(T):
  # 초기화
  ## 가로, 세로, 배추 개수
  m, n, k = map(int, input().split())
  farm = [[0] * m for _ in range(n)]  
  visited = [[False] * m for _ in range(n)]  
  q = deque([])
  cabbageq = deque([])
  for i in range(k):
    y, x = map(int, input().split())
    farm[x][y] = 1
    cabbageq.append((x, y))

  worm = 0
  while cabbageq:
    x, y = cabbageq.popleft()
    if farm[x][y] == 1 and not visited[x][y]:
      visited[x][y] = True
      q.append((x, y))
      
      while q: 
        x, y = q.popleft()
        for i in range(4):
          nx = x + dx[i]
          ny = y + dy[i]
          if 0 <= nx < n and 0 <= ny < m:
            if farm[nx][ny] == 1 and not visited[nx][ny]:
              visited[nx][ny] = True
              q.append((nx, ny))
              
      worm += 1
  
  print(worm)

 

: 큐에 넣을 때 해당 위치를 방문해줘야 중복 처리가 일어나지 않는데, 뺄 때 방문 처리를 했기 때문에 오류가 난 것이었습니다.

: 와 .. 정말 모르고 실전 들어갈 뻔한 내용입니다.

: 힌트는 백준 해당 문제 토론방에 올라온 링크에서 찾을 수 있었습니다.

 

: https://www.acmicpc.net/blog/view/70

자주 틀리는 요인

라고 합니다.

혹시나싶어 내 코드를 살펴봤습니다. 사실 혹시나도 아니고 역시나겠지하며 살펴봤습니다.

코드 짤 때부터 넣을 때 방문할까? 나올 때 방문할까? 고민하다가,

둘 다 결과는 '똑같겠지 머~' 이러면서 안일하게 풀었기 때문입니다.

 

중복 방문이 일어난 것이었습니다. 참고로 저 링크의 내용들은 제가 한 번씩 틀려본 내용이 많이 들어있었습니다. 아닌 내용은 앞으로 틀릴 것 같이 보였구요. 혼자 공부하는 사람으로써 저한테는 저런 글 하나하나가 귀중한 글들입니다. 정보 공유하는 많은 분들의 선의에 감사한 마음으로 열심히 공부하겠습니다. 

 

: 하여간 구현 자체는 어렵지는 않게 느껴졌습니다. 

: 문제 풀이 전에 BFS 개념을 되짚고 풀기 시작해서 그런 것 같습니다. 순간 BFS 뭐지 싶었거든요. 하하ㅏ하... 😅