백준 2667 - 파이썬

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

문제 풀이

이 문제는 BFS와 DFS를 응용하여 풀이하는 문제이다. 두 가지 방법 중 BFS를 선택해 구현을 진행하였고, 첫번째 단지를 바로 찾을 수 있었다. 

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

n = int(input().rstrip())

graph = []

for _ in range(n):
  graph.append(list(map(int, input().rstrip())))

def bfs(x, y):
  dx = [-1, 1, 0, 0]
  dy = [0, 0, -1, 1]

  q = deque()
  q.append((x,y))

  graph[x][y] = 0
  count = 1

  visited = [[0] * n for _ in range(n)]
  
  while q:
    x, y = q.popleft()
    
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
  
      if nx < 0 or nx >= n or ny < 0 or ny >= n:
        continue

      if graph[nx][ny] == 0:
        continue
  
      if graph[nx][ny] == 1 and visited[nx][ny] == 0:
        visited[nx][ny] = 1
        q.append((nx, ny))
        count += 1

  return count

print(bfs(0,0))

하지만 다른 단지를 찾는데 좀 오래 걸렸던거 같다. 가장 먼저 시작지점을 (0,0), (0,n), (n,0), (n,n) 이렇게 네 곳으로 시작하면 다 찾을 수 있지 않을까 싶어 구현을 해 봤는데 아쉽게도 단지를 전부 찾지 못했다. 그래서 좀 더 효율적인 방법은 없을까 고민하다가 BFS() 함수를 호출할 때마다 1이 존재하는 인덱스의 값을 넣어주면 좋을거 같다는 생각이 들어 실행에 옮겨보았고, 전혀 다른 값이 출력되어 뭐가 문제일까 찾아보다가 visited 리스트에 값을 저장하는 식으로 풀이를 하고 인덱스를 찾을때는 graph 리스트로 찾아서 잘못 출력됨을 알게 되었다.

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

n = int(input().rstrip())

graph = []

for _ in range(n):
  graph.append(list(map(int, input().rstrip())))

def bfs(x, y):
  dx = [-1, 1, 0, 0]
  dy = [0, 0, -1, 1]

  q = deque()
  q.append((x,y))

  graph[x][y] = 0
  count = 1
  
  while q:
    x, y = q.popleft()
    
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
  
      if nx < 0 or nx >= n or ny < 0 or ny >= n:
        continue

      if graph[nx][ny] == 0:
        continue
  
      if graph[nx][ny] == 1:
        graph[nx][ny] = 0
        q.append((nx, ny))
        count += 1

  return count

cnt = []

for i in range(n):
  for j in range(n):
    if graph[i][j] == 1:
      cnt.append(bfs(i, j))

cnt.sort()

print(len(cnt))

for i in range(len(cnt)):
  print(cnt[i])

 

이번 문제를 풀면서 느낀점은 항상 느끼는 것이지만 조금만 생각의 틀을 바꿔보고, 생각해보려고 하면 풀 수 있었다는 점이다. 사실 이 부분은 갑자기 확 되는게 아니니 조금씩 노력하면서 생각하는 힘을 길러봐야 되겠다.