[Python][백준 2234][BFS] 성곽 - 컴도리돌이

반응형

---

풀이 과정

본 문제는 전형적인 BFS문제이다. 

왜냐하면 연결되어 있는 방의 개수를 물어봤기 때문이다.

 

부가적으로 특이한 요소를 첨가하였다.

각 좌표들 간에 연결되었는지를 

15 이하의 값으로 주어져있다.

0~15 (?)

문제에서 언급한 힌트대로 이 문제는

좌표 이동을 비트 마스킹을 해준다.

 

하지만 비트 마스킹이 익숙하지 않아서,,,

나는 문자열로 표시를 하였다.

물론 하는 방법은

비트 마스킹이랑 똑같다..!

"0000" ~ "1111" 

맨 왼쪽부터 서북 동남을 의미하고

1은 이동 불가(벽으로 연결)를 의미하고

0은 이동 가능을 의미한다.

 

1. m*n 만큼 반복문을 돌려서 해당 (i, j) 위치를

방문하지 않을 경우 BFS 탐색을 한다.

 

2. 현재 위치 값을 bin함수를 이용하여 이진수를 나타내고

크기를 4로 맞춰준다.(동서남북으로 쉽게 표현하려고)

 

3. 다음 위치 값에 방문하지 않고 이동하지 않을 경우

q에 삽입한다.

 

4. bfs 함수에서 부가적으로 한 작업이 있는데,

탐색한 경로들을 반복문을 돌려서

"roomCntBoard"에 해당 좌표를 key로, value를 방의 크기로 설정하였다.

(추후에 두 개의 인접한 방들의 합 중에서 제일 큰 값을 선정하기 위해서)

 

5. m*n*4 반복문을 돌린다.

현재 좌표에서 동서남북으로 탐색을 하는데,

방 번호가 다를 경우 두 방 크기의 합을

"roomCombinationList"에 삽입한다.

 

6. 문제의 요구사항 출력

roomCnt -> 방의 개수

roomMaxValue -> 방들의 크기 리스트(max 값 출력)

roomCombinationList -> 인접한 두 방의 크기 합 리스트(max 값 출력)

 

한번에 문제가 해결되어서 코드가 조금 지저분하다..

미안합니다.🥲🥲🥲

---

풀이 코드

from collections import deque

n,m = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(m)]
visited,dx,dy = [[0] * n for _ in range(m)],[0,-1,0,1],[-1,0,1,0]
roomCntBoard = {}
roomCnt = 1
roomMaxValue = []
roomCombinationList = set()

def bfs(x,y,color) :
  visited[x][y] = color
  q = deque([(x,y)])
  boardColor = []
  while q :
    x,y = q.popleft()
    binary = bin(board[x][y])[2:]
    binary = '0' * (4-len(binary)) + binary
    b = list(map(int,binary))
    b.reverse()
    boardColor.append((x,y))
    for i in range(4) :
      nx,ny = x + dx[i],y + dy[i]
      if not b[i] and 0<= nx < m and 0<= ny < n and  not visited[nx][ny] :
        visited[nx][ny] = color
        q.append((nx,ny))
  cnt = len(boardColor)
  for x,y in boardColor :
    roomCntBoard[(x,y)] = cnt
  return cnt
  
for i in range(m) :
  for j in range(n) :
    if not visited[i][j] :
      roomMaxValue.append(bfs(i,j,roomCnt))
      roomCnt +=1

for i in range(m) :
  for j in range(n) :
    color = visited[i][j]
    for k in range(4) :
      ni,nj = i + dx[k], j + dy[k]
      if 0<= ni < m and 0 <= nj < n and color != visited[ni][nj] :
        roomCombinationList.add(roomCntBoard[(i,j)] + roomCntBoard[(ni,nj)])

print(roomCnt - 1)
print(max(roomMaxValue))
print(max(roomCombinationList))