16946-벽 부수고 이동하기 4

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

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

겉으로 보면 간단해 보이지만 굉장히 시간초과가 많이 발생하는 문제였다. 처음부터 문제의 조건과 각 풀이방법별 예상 시간 복잡도를 계산해본 후 코드작성에 들어가야 헤매지 않을 수 있는 문제인것 같다.

 

먼저 문제의 설명과 예시를 보면 가장 먼저 생각나는게 BFS일테고, 각 좌표별로 BFS를 돌려 카운트를 세면 당연히 시간초과가 난다. N by M 행렬이고 N과 M은 각각 10^3까지 가능하니 좌표의 최대 갯수는 10^6개, 이를 시간복잡도 O(N^2) 형태의 알고리즘을 사용하면 풀 수 없다는 것을 예측할 수 있다. 중복을 최대한 줄일 수 있는 다른 방식이 필요하다.

 

먼저 비어있는 공간마다 이동할 수 있는 경로의 수를 세서 새로운 행렬을 만들어 놓는 방식을 사용하였다.

1 1 0 0 1              -1 -1  2  2 -1   

0 0 1 1 1       ->     3  3 -1 -1 -1

0 1 0 1 0               3 -1  1 -1  1

1 0 1 0 1              -1  1 -1  1 -1

이런 형식이다. 여기서 초기 숫자들은 모두 문자의 형태로 받아서 '1' '0' 이런 상태였기 때문에 굳이 -1로 바꾸지 않아도 된다. 

 

이제 이 상태에서 -1인 값들만 접근해 주변에 숫자가 있으면 이를 더해주는 방식으로 코드를 구성하였는데 틀렸습니다가 나왔다. 생각해보니 상하좌우 좌표들 중 서로 이어진게 있으면 중복으로 덧셈이 되는 상황이었다. 그렇다고 전후좌우 중 서로 다른 숫자일때만 덧셈을 하는것도 반례가 존재한다.(ex.왼쪽으로 쭉 3개가 이어져 있고 동시에 오른쪽으로 3개가 이어져 있는 경우) 따라서 각 공유블록당 구분할 수 있는 숫자를 추가로 삽입해 주어야겠다는 생각이 들었다.

1 1 0 0 1                 -1    -1   (1,2)  (1,2)  -1 

0 0 1 1 1       ->     (2,3)  (2,3)   -1     -1   -1

0 1 0 1 0               (2,3)   -1   (3,1)    -1  (4,1)

1 0 1 0 1                -1    (5,1)  -1    (6,1)  -1

이런식으로 저장하면 이제 -1을 기준으로 전후좌우 중 튜플의 첫째값이 다를때만 값을 더해서 결과값을 도출할 수 있다.

 

추가적으로 출력 방식이나 %를 이용한 나머지 계산 등의 디테일을 추가하면 이제 시간초과에 걸리지 않고 문제를 해결 가능하다..!

 

import sys
input = sys.stdin.readline
from collections import deque
N, M = map(int,input().split())
adj =[]
for _ in range(N):
    adj.append(list(str(input().strip())))

dy = (0,1,0,-1)
dx = (1,0,-1,0)

def chkadj(x, y):
    if 0<= x < N and 0<= y < M:
        return True

def bfs(x, y, cnt):
    count = 1
    dq = deque()
    dq.append((x,y))
    chk[x][y] = cnt
    while dq:
        nowx, nowy = dq.popleft()
        for i in range(4):
            nx, ny = nowx+dx[i], nowy+dy[i]
            if chkadj(nx,ny) and chk[nx][ny] != cnt and adj[nx][ny] != '1' :
                if adj[nx][ny] != '0':
                    return (adj[nx][ny])
                count += 1
                chk[nx][ny] = cnt
                dq.append((nx,ny))
    return (cnt,count)

chk = [[0]*M for _ in range(N)]    
cnt = 1
for i in range(N):
    for j in range(M):
        if adj[i][j] != '1':
            adj[i][j] = bfs(i,j,cnt)
            cnt += 1

ans = [[]for _ in range(N)]
for x in range(N):
    for y in range(M):
        if adj[x][y] == '1':
            tmp = []
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if chkadj(nx,ny) and adj[nx][ny] != '1' and adj[nx][ny] not in tmp:
                    tmp.append(adj[nx][ny])            
            sumtmp= 0
            #print(tmp)
            for i in tmp:
                sumtmp += i[1]
            ans[x].append(int(sumtmp+1)%10)
        else:
            ans[x].append(0)
        
for i in range(N):
    for j in range(M):
        print(ans[i][j], end='')
    print()