[Python] 백준 16946 - 벽 부수고 이동하기 4

https://www.acmicpc.net/problem/16946

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

 

 

전체적인 로직은 다른 사람들도 쉽게 잡았을거라고 생각한다.

그래서 쉽게 풀 수 있을 것이라 생각했는데 풀고 제출하니 시간초과;;

 

알고리즘은 다음과 같다

 

0. 벽으로 둘러싸인 빈 공간을 하나의 구역으로 취급한다.

1. BFS를 통해 각 구역의 빈 칸 개수를 따로 저장한다. (난 area 딕셔너리에 저장했다.)

2.  방문 처리를 위한 visited에는 구역의 번호를 저장한다.

3. 1~2를 통해 모든 구역을 탐색한다.

4. 이제 순차적으로 벽을 탐색한다.

5. 벽의 상하좌우를 살펴보며 각 구역의 번호를 set 자료구조에 저장한다. (중복되는 구역 방지 위함)

6. set에 저장된 각 구역에 매칭되는 빈 칸의 개수를 해당 벽에 더해준다. (area 딕셔너리에서 매칭 비교)

7. 5~6을 반복한다.

 

딕셔너리와 set 자료구조를 사용해서 시간초과를 벗어날 수 있었다.

 

from collections import deque

def bfs(start, num):
    q = deque() 
    q.append(start)

    cnt = 1
    while q:
        x,y = q.popleft()

        for dx,dy in zip(dxs,dys):
            nx,ny = x+dx, y+dy
            # 범위 내에 있고 빈 공간이며, 방문을 한 적 없다면
            if 0<=nx<n and 0<=ny<m and grid[nx][ny]==0 and visited[nx][ny] == 0:
                visited[nx][ny] = num
                cnt+=1
                q.append((nx,ny))

    return cnt
                
                            

n,m = map(int,input().split())
grid = [list(map(int,input())) for _ in range(n)]
visited = [[0 for _ in range(m)] for _ in range(n)]

dxs, dys = [1,-1,0,0], [0,0,1,-1]

area = {}
area[0] = 0

# 각 구역의 빈 칸 정보 저장
num = 1
for x in range(n):
    for y in range(m):
        if grid[x][y] == 0 and visited[x][y] == 0:
            visited[x][y] = num
            cnt = bfs((x, y), num)
            area[num] = cnt

            num+=1
            

for x in range(n):
    for y in range(m):
        if grid[x][y] == 1:
            
            # 중복되는 구역의 빈칸을 더하는 것 방지.
            ss = set()

            # 벽인 부분의 상하좌우 확인
            for dx,dy in zip(dxs,dys):
                nx,ny = x+dx, y+dy
                if 0<=nx<n and 0<=ny<m and grid[nx][ny] == 0:
                    ss.add(visited[nx][ny])
            
            # 각 구역의 빈 칸을 더하기
            for s in ss:
                grid[x][y] += area[s]

            grid[x][y] %= 10


for i in grid:
    print("".join(map(str, i)))

 

더 열심히 공부하자.