백준 BOJ 16946
BFS [G2]벽 부수고 이동하기4 16946
문제 링크
난이도 : Gold 2
Issue
벽을 만난 후 BFS, DFS 시간 초과
벽을 만날때 마다 연결 통로를 중복 BFS 하는 문제가 발생
오랜만에 알고리즘..
오랜만에 BFS.. 가 이슈
Soln
벽이 아닌 연결된 통로를 BFS로 탐색 후,
다시 재 탐색 하지 않게 만들어야 함.
Detail
- 연결된 통로를 그룹화
- BFS 탐색 시, 인접한 좌표에 연결통로를 update
문제 링크
난이도 : Gold 2
벽을 만난 후 BFS, DFS 시간 초과
벽을 만날때 마다 연결 통로를 중복 BFS 하는 문제가 발생
오랜만에 알고리즘..
오랜만에 BFS.. 가 이슈
벽이 아닌 연결된 통로를 BFS로 탐색 후,
다시 재 탐색 하지 않게 만들어야 함.
- 연결된 통로를 그룹화
- 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)))
Author And Source
이 문제에 관하여(백준 BOJ 16946), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@minchjung/BOJ-16946저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)