[백준/그래프] 16946번 벽 부수고 이동하기 4

 

 

 

방법1. 한 칸마다 BFS를 이용해서, 1인 벽을 기준으로, 벽을 뚫고 갈 수 있는 칸의 횟수를 센다.

처음에 이 방법을 생각하고, 제출했더니 시간초과가 떴다....

N 이 1000, M이 1000 이하여서, 한 칸씩마다 BFS 를 하면 10 ^ 6 번을 그래프 탐색하므로 그런 것 같다.

import sys
from collections import deque

input = sys.stdin.readline

dx = [1,-1,0,0]
dy = [0,0,1,-1]

n,m = map(int,input().split())

Map = [list(input().strip()) for _ in range(n)]
ans = [['0'] * m for _ in range(n)]


def BFS(x,y):
    check = [(x,y)]
    q = deque([(x,y)])
    cnt = 1

    while q:
        x,y = q.pop()
        for i in range(4):
            a = x + dx[i]
            b = y + dy[i]

            if 0<=a<n and 0<=b<m and Map[a][b] == '0':
                if (a,b) not in check:
                    q.append((a,b))
                    check.append((a,b))
                    cnt += 1
    return str(cnt)

for i in range(n):
    for j in range(m):
        if Map[i][j] == '1':
            ans[i][j] = BFS(i,j)
                    

for i in range(n):
    print(''.join(ans[i]))

방법 2. 0을 기준으로, 벽이 아닌 땅끼리 묶어주고 이 때 땅에 index를 주어서 땅의 면적을 저장한다.

그리고, 1인 지점에서 상하좌우 탐색해서 합해보자.

 

무엇을 고려해주지 못했는지, 계속 틀렸습니다...

뭐가 틀렸을까..

import sys
from collections import deque

n,m = map(int,input().split())
Map = [list(input().strip()) for _ in range(n)]
size = []
ans = [['0'] * m for _ in range(n)]

dx = [1,-1,0,0]
dy = [0,0,1,-1]

#땅 면적 구하기
index = 2
for i in range(n):
    for j in range(m):
        if Map[i][j] == '0':
            cnt = 1
            Map[i][j] = str(index)
            q = deque([(i,j)])

            while q:
                x,y = q.pop()
            
                for k in range(4):
                    a = i+dx[k]
                    b = j+dy[k]

                    if 0<=a<n and 0<=b<m:
                        if Map[a][b] == '0':
                            q.append((a,b))
                            Map[a][b] = str(index)
                            cnt += 1
            size.append(cnt)
            index += 1


#한 지점에서 땅 상하좌우 연결 확인
for i in range(n):
    for j in range(m):
        #벽일때
        if Map[i][j] == '1':
            cnt = 1
            check = '1'
            for k in range(4):
                a = i+dx[k]
                b = j+dy[k]

                if 0<=a<n and 0<=b<m:
                    if Map[a][b] not in check:
                        check += Map[a][b]
                        cnt += size[int(Map[a][b])-2]
            ans[i][j] = str(cnt%10)

for i in range(n):
    print(''.join(ans[i]))

 

index map을 따로 만들어서 했는데, 맞았다. 

위에 것이랑 뭐가 다른데.. 예시가 생각나면 적어야겠다..

import sys
from collections import deque

input = sys.stdin.readline

n,m = map(int,input().split())
Map = [list(input().strip()) for _ in range(n)]

#ans, visin, index, area
ans = [['0']*m for _ in range(n)]
index = [[0]* m for _ in range(n)]
area = [0,]

dx = [1,-1,0,0]
dy = [0,0,1,-1]

#면적 indexing 과 크기
num = 1
for i in range(n):
    for j in range(m):
        if (Map[i][j] == '0') and (index[i][j] == 0):
            cnt = 1
            q = deque([(i,j)])
            index[i][j] = num

            while q:
                x, y = q.pop()

                for k in range(4):
                    a = x + dx[k]
                    b = y + dy[k]

                    if 0<=a<n and 0<=b<m:
                        if (Map[a][b] == '0') and (index[a][b] == 0):
                            q.append((a,b))
                            index[a][b] = num
                            cnt += 1

            area.append(cnt)
            num += 1

#벽 부시기
for i in range(n):
    for j in range(m):
        if Map[i][j] == '1':
            cnt = 1
            check = []
            for k in range(4):
                a = i + dx[k]
                b = j + dy[k]

                if 0<=a<n and 0<=b<m:
                    if index[a][b] not in check:
                        cnt += area[index[a][b]]
                        check.append(index[a][b])
            ans[i][j] = str(cnt%10)

for i in range(n):
    print(''.join(ans[i]))