BFS [G2]벽 부수고 이동하기4 16946

문제 링크
난이도 : Gold 2

Issue

벽을 만난 후 BFS, DFS 시간 초과
벽을 만날때 마다 연결 통로를 중복 BFS 하는 문제가 발생
오랜만에 알고리즘..
오랜만에 BFS.. 가 이슈

Soln

벽이 아닌 연결된 통로를 BFS로 탐색 후,
다시 재 탐색 하지 않게 만들어야 함.

Detail

1. 연결된 통로를 그룹화
2. BFS 탐색 시, 인접한 좌표에 연결통로를 update

시간 초과 후에, 1번의 그룹화 방식 Hash map, key-val 형태로 많이 사용함을 참조 했다. 그런데, 일반적인 BFS 탐색을 해주면서 벽에 가능한 연결 통로 갯수를 중복되지 않게 카운트만 해주면 될것 같았다. (한번 검색으로 끝내고 싶은..), 그런데 조금 비효율적이다. ㅠ.

벽이 아닌 케이스를 BFS 탐색 하면서, 벽일때 좌표를 기록해 두었다. 그리고, BFS를 마치고 나왔을때 해당 누적 경로를 계속해서 + 해주는 방식. 어차피 벽좌표를 다시 루프를 돌려야 하는데 .. 시간 초과는 뜨지 않아 일단 pass...

시간 초과 코드

N, M = map(int, input().split())
board = [ list(map(int, input())) for _ in range(N) ]
vis = [ [False]*M for _ in range(N) ]
ans = [ m[:] for m in board ]
dirX = [0,0,1,-1]
dirY = [1,-1,0,0]
cnt = 0

def DFS (curX,curY) : 
  global cnt 
  if cnt > 10 : return 
  for d in range(4) : 
    nxtX = curX + dirX[d]; nxtY = curY + dirY[d]
    if nxtX < 0 or nxtY < 0 or nxtX >= N or nxtY >= M : continue 
    if vis[nxtX][nxtY] or board[nxtX][nxtY] : continue 
    vis[nxtX][nxtY] = True 

    DFS(nxtX, nxtY)
    cnt += 1 
  return 

for r in range(N) : 
  for c in range(M) : 
    if not board[r][c] : continue  
    vis = [ [False]*M for _ in range(N) ]
    board[r][c] = 0 
    DFS(r,c)
    ans[r][c] = cnt % 10
    cnt = 0
    board[r][c] = 1

for a in ans : print(''.join(map(str, a)))

통과 코드

from collections import deque 

N, M = map(int, input().split())
board = [ list(map(int, input())) for _ in range(N) ]

vis = [ [False]*M for _ in range(N) ]
ans = [ m[:] for m in board ]
dir = [ [0,1],[0,-1],[1,0],[-1,0] ]

for r in range(N) : 
  for c in range(M) : 
    if not board[r][c] and not vis[r][c] : 
      q = deque()
      q.append([r,c])
      cnt = 1
      ones = [] 
      vis[r][c] = True
      
      while q : 
        curR, curC = q.popleft() 
        for x , y  in dir : 
          nxtR = curR + x
          nxtC = curC + y
          if nxtR < 0 or nxtC < 0 or nxtR >= N or nxtC >= M : continue 
          if vis[nxtR][nxtC] : continue 
          vis[nxtR][nxtC] = True 
          if not board[nxtR][nxtC] :
            cnt +=1 
            q.append([ nxtR, nxtC ])
          else : 
            ones.append([ nxtR, nxtC ])
      
      for nxtr, nxtc in ones :
        vis[nxtr][nxtc] = False 
        ans[nxtr][nxtc] += cnt 
        ans[nxtr][nxtc] %= 10 

for a in ans : print(''.join(map(str, a)))

정답 코드