[bfs/백준] 16946번 : 벽 부수고 이동하기 4 (itr)

- 문제 : https://www.acmicpc.net/problem/16946

 

Gold Level2 문제

쉽다고 생각한 문제였다. 1인 지점을 기준으로 주변의 0의 갯수를 세는 bfs를 실행한 다음 그 갯수를 그 위치값에 넣는 식으로 진행했다 

그랬더니 계속 시간초과 문제가 나서 이전 풀이를 다시 보았다 

 

위 방법으로 진행하면 시간초과가 나므로 관점을 바꿔서 0을 정점으로 보고 연결요소들의 크기를 계산하는 것이다.

각 연결요소를 구할 때 인접한 벽들을 기억하고 있다가 연결요소를 모두 구했을 때 그 크기를 기억해둔 벽들의 좌표에 더해주는 방식으로 진행해 주면 된다 

 

참고한 블로그

 

다른 부분은 다 이해가는데, 유독 itr인 부분이 이해가지 않는다 

해당 bfs에 있지만, 아직 방문하지 않은 노드에 대해서 0이면 탐색 진행하고, 1이면 temp에 삽입한다 

bfs를 실행한 뒤 iter += 1을 하는 것으로 보아 0의 갯수를 세는 것 같다 

 

하나의 0이 영향을 미칠 수 있는 1의 갯수는 여러개이므로 visit 값이 0,1이 아닌 itr로 이루어진건가??

그래야지 각 bfs를 거치면서 0을 중복으로 셀 수 있으니까

 

- 정답 풀이 :

from collections import deque

n,m = map(int,input().split())
data = [list(map(int, input())) for _ in range(n)]
visit = [[0]*m for _ in range(n)]
answer = [[0]*m for _ in range(n)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x,y,itr):    
    visit[x][y] = itr
    queue=deque()
    queue.append((x,y))
    count = 1
    temp = []
    while queue: 
        x,y = queue.popleft()
        for i in range(4):
            nx,ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and visit[nx][ny] != itr:
                #0인 경우
                if not data[nx][ny] :  
                    visit[nx][ny] = itr
                    #0의 갯수 세기
                    count += 1
                    queue.append((nx,ny))
                #1인 경우
                else: 
                    temp.append([nx,ny])
                    visit[nx][ny] = itr
    for i,j in temp:
        answer[i][j] += count
        
for i in range(n):
    for j in range(m):
        if data[i][j]:
            answer[i][j] = 1
itr = 1            
for i in range(n):
    for j in range(m):
        #방문하지 않았고, 0인 위치에 대해서 bfs 진행
        if not data[i][j] and not visit[i][j]:
            bfs(i,j,itr)
            itr += 1
            
for i in range(n):
    for j in range(m):
        print(answer[i][j] % 10, end='')
    print()

 

- 시도해본 풀이 

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

n,m = map(int,input().split())
data = [list(input()) for _ in range(n)]
answer = [[0]*m for _ in range(n)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x,y,data):
    visit = [[0]*m for _ in range(n)]
    visit[x][y] = 1
    queue=deque()
    queue.append((x,y))
    count = 1
    while queue: 
        x,y = queue.popleft()
        for i in range(4):
            nx,ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if data[nx][ny] == '0' and not visit[nx][ny]:
                    visit[nx][ny] = 1
                    count += 1
                    queue.append((nx,ny))
    return str(count)

answer = 0 
for i in range(n):
    for j in range(m):
        if data[i][j] == '1':
            answer = bfs(i,j,data)
            data[i][j] = answer

for i in range(n):
    temp=''
    for j in range(m):
        temp += data[i][j]
    print(temp)