[BOJ/백준] 16946 벽 부수고 이동하기 4

# 16946 벽 부수고 이동하기 4

# dfs를 해준다. 여기서 일반적인 dfs와 다른점은 방문표시 대신 해당 위치의 값을 들어온 index값으로 변형시켜준다.
def dfs(x,y,index):
    global index_dict,N,M

    stack = [(x,y)]
    cnt = 1
    arr[x][y] = index
    while stack:
        cx,cy = stack.pop()
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0<=nx<N and 0<=ny<M:
                if not arr[nx][ny]:
                    stack.append((nx,ny))
                    arr[nx][ny] = index
                    cnt += 1
    # dfs를 전부 한뒤에 그 개수를 딕셔너리에 저장해준다.
    index_dict[index] = cnt




# dfs를 이용해서 쉽게 풀수 있었던 문제


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

dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(map(int,list(input()))) for _ in range(N)]
# 원본이 저장된 arr
result = [['0']*M for _ in range(N)]
# 결과값들을 저장해놓는 result 배열을 만들어둔다.

# 빈칸인 개수를 세주기 위해서 초기값을 -1로 해줬다. 왜냐하면 arr에는 1,0이 있으므로 겹쳐지지 않게 -1부터 시작해서 1씩 작아지게 해줬다.
# 그리고 해당 인덱스에 연결된 개수를 저장하기 위한 index_dict라는 딕셔너리를 미리 만들어줬다.
index = -1
index_dict = {}

# 빈칸의 개수를 세어주기 위한 dfs 공정
for x in range(N):
    for y in range(M):
        if not arr[x][y]:
            dfs(x,y,index)
            index -= 1

for x in range(N):
    for y in range(M):
        if arr[x][y] == 1:
            # 원본 배열에서 벽이 있을때, 그 벽 주변의 상황을 파악하고, 그 중에 1이 아닌 우리가 설정한 index값을 집합에 저장해준다.
            temp = set()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<N and 0<=ny<M:
                    if arr[nx][ny] != 1:
                        temp.add(arr[nx][ny])
            # 기본값은 1이고, temp에 저장된 index들을 반복문을 돌려 움직일수 있는 칸의 개수를 세준다.
            move_wall = 1
            for index in temp:
                move_wall += index_dict[index]
            # 그리고 result에 10으로 나눈 나머지를 string형태로 저장해준다.
            result[x][y] = str(move_wall%10)
# join을 이용해 출력해준다.
for row in result:
    print(''.join(row))

 이 문제는 union find 문제와 비슷하게 빈 위치의 그룹을 지어주면 된다.

 

최종 결과가 나올 result라는 2차원 배열을 '0'으로 초기화 해줬다. 왜냐하면, 나중에 출력을 할때, join을 쓰기 위해, 문자열 형태로 초기화 해줬다.

 

먼저 주어진 행렬의 빈칸들의 그룹의 정보를 저장해줄 index_dict을 만들어줬다. 여기서 key는 index 을 기준으로 해줬고, value는 그 그룹의 개수이다.

 

여기서 index 초기값을 -1을 해준 이유는 문제에서 0,1을 이미 쓰고 있어서, 겹치지 않기 위해 음수로 해줬다.

 

그러면 주어진 행렬에서 dfs 아니면 bfs를 해주면서, 빈칸들의 그룹들을 나눠 주는 작업을 해주고, 그 그룹의 크기와 index를 index_dict에 저장을 해주면서, 원본행렬에도 index를 대신 넣어준다.

 

 

벽 부수고 이동하기를 해주는 방법은 원본 행렬에서 1인 곳을 찾아서, 상하좌우에 있는 1이 아닌 값들을 집합에 저장을 해준다. 그리고 집합에 저장된 index들을 꺼내 전체 index_dict에 저장된 값들을 더해주면 된다. 그리고 원래 있던 벽이 무너지는 거니 1이 기본값이다.

 

그리고 결과값을 10으로 나눈 나머지를 문자열 형태로 저장해줬다.