[백준] [BFS] [그룹화] 16946. 벽 부수고 이동하기 4

16946. 벽 부수고 이동하기 4

16946번: 벽 부수고 이동하기 4

 

주요 풀이 방식

• 📍NxM 이 1000x1000
  • 일반적으로 graph 값이 1일때마다 BFS를 돌리면 시간초과
    • 앞에서 개수 셌던 것을 다른 위치에서 반복해서 세기 때문
  • 연결된 0끼리 그룹을 만들어서 각 그룹의 0개수를 한번만 저장해두고 사용
  • 📍값 계산할때 중복된 그룹을 다른 방향에서 만날 수 있음 -> 계산한 그룹은 반복계산하지 않도록 처리
    • in /not in 사용할때 리스트가 아닌 set()을 사용해서 O(1)

 

• 내 풀이
  • 풀이 참고

from collections import deque

#0 그룹화
def bfs(i,j):
    global flag
    global cnt
    
    queue.append((i,j))
    visited[i][j]=flag
    
    while queue:
        x,y=queue.popleft()
    
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
      
            if nx<0 or nx>=r or ny<0 or ny>=c: continue
            if graph[nx][ny]==0 and visited[nx][ny]==0:
                visited[nx][ny]=flag
                cnt+=1 #그룹 별 개수
                queue.append((nx,ny))
    return

def solve(x,y):
    check=set() #중복 그룹 처리
    answer[x][y]+=1
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
    
        if nx<0 or nx>=r or ny<0 or ny>=c: continue
        if visited[nx][ny] not in check and graph[nx][ny]==0:
            k=visited[nx][ny]
            check.add(k)
            answer[x][y]+=lst[k]

r,c=map(int,input().split())
graph=[list(map(int,input().rstrip())) for _ in range(r)]
queue=deque()
dx=[-1,1,0,0]
dy=[0,0,-1,1]

flag=0
visited=[[0 for _ in range(c)] for _ in range(r)]
answer=[[0 for _ in range(c)] for _ in range(r)]
lst={} #그룹별 0 개수

for i in range(r):
    for j in range(c):
        if graph[i][j]==0 and visited[i][j]==0:
            cnt=1
            flag+=1 #그룹 번호
            bfs(i,j)
            lst[flag]= cnt #각 그룹별 0개수 저장

#결과 계산
for i in range(r):
    for j in range(c):
        if graph[i][j]==1:
            solve(i,j)

#출력
for i in range(r):
    for j in range(c):
        print(answer[i][j]%10, end="")
    print()

 

 

• 다른 사람 풀이

from collections import defaultdict, deque

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

N, M = map(int, input().split())

graph = []

dic = defaultdict(int)

empty_graph = [[0 for i in range(M)] for j in range(N)]

for _ in range(N):
    graph.append(input())

q = deque()
num = 1

for row in range(N):
    for col in range(M):
        if graph[row][col] == '1':  # 벽이면 통과
            continue
        if empty_graph[row][col] != 0:  # 이미 방문했으면 통과
            continue

        max_value = 0
        q.append((row, col))
        empty_graph[row][col] = num

        while q:
            c_row, c_col = q.popleft()
            max_value += 1
            for i in range(4):
                n_row = c_row + dr[i]
                n_col = c_col + dc[i]
                if n_row < 0 or n_col < 0 or n_row >= N or n_col >= M:
                    continue
                if graph[n_row][n_col] == '1':  # 벽이면 통과
                    continue
                if empty_graph[n_row][n_col] != 0:  # 이미 방문했으면 통과
                    continue
                empty_graph[n_row][n_col] = num
                q.append((n_row, n_col))

        dic[num] = max_value

        num += 1

answer = [[1 for i in range(M)] for j in range(N)]
# print(empty_graph)
for row in range(N):
    for col in range(M):
        #print(row, col)
        # print(graph[row][col])
        if graph[row][col] == '0':
            answer[row][col] = 0
        else:
            # print("wall")
            s = set()
            for i in range(4):
                n_row = row + dr[i]
                n_col = col + dc[i]
                if n_row < 0 or n_col < 0 or n_row >= N or n_col >= M:
                    continue
                #print("row,col", n_row, n_col)
                s.add(empty_graph[n_row][n_col])
            for i in s:
                answer[row][col] += dic[i]
            answer[row][col] = answer[row][col] % 10

for i in range(N):
    print(''.join(str(s) for s in answer[i]))