[백준/파이썬] 16946: 벽 부수고 이동하기 4

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

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

문제 요약 : NxM 맵이 있다. 0은 이동할 수 있는 칸을 나타내고, 1은 벽을 나타낸다. 0은 그대로 출력하고, 벽은 해당 벽을 부수었을 때 이동할 수 있는 칸의 수를 10으로 나눈 나머지를 출력하라.

 

예제 입력1 :

3 3
101
010
101

예제 출력 1:

303
050
303

 

시도 1 )

dfs로 풀기!

당연히 골드2가 고작 dfs로 끝날리 없지만,, 일단 dfs로 풀어보았다.

# 벽 부수고 이동하기 4
N, M = map(int,input().split())
Map = [list(map(int, input())) for _ in range(N)]

def dfs(Map, sx, sy):
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    stack = [[sx,sy]]
    visit = list([True]*M for _ in range(N))
    count = 0
    
    while stack :
        x, y = stack.pop()
        if visit[x][y] == True :
            count += 1            
            visit[x][y] = False
            for i in range(4):
                ix = x + dx[i]
                iy = y + dy[i]
                if N > ix >= 0 and M > iy >= 0 and visit[ix][iy] == True and Map[ix][iy] == 0:
                    stack.append([ix,iy])
    return count

for i in range(N):
    for j in range(M):
        if Map[i][j] == 1 :            
            Map[i][j] = 0
            Map[i][j] = dfs(Map,i,j)%10

for k in Map :
    print(*k,sep='')

시간초과가 떴다 ㅎㅅㅎ

 

시도 2 )

혹시나해서 bfs로 풀어보았다.

# 벽 부수고 이동하기 4
from collections import deque

N, M = map(int,input().split())
Map = [list(map(int, input())) for _ in range(N)]

def bfs(Map, sx, sy):
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    queue = deque([[sx,sy]])
    visit = list([True]*M for _ in range(N))
    count = 0
    
    while queue :
        x, y = queue.popleft()
        if visit[x][y] == True :
            count += 1            
            visit[x][y] = False
            for i in range(4):
                ix = x + dx[i]
                iy = y + dy[i]
                if N > ix >= 0 and M > iy >= 0 and Map[ix][iy] == 0:
                    queue.append([ix,iy])
    return count

for i in range(N):
    for j in range(M):
        if Map[i][j] == 1 :            
            Map[i][j] = 0
            Map[i][j] = bfs(Map,i,j)%10

for k in Map :
    print(*k,sep='')

당연히 시간초과..ㅎㅎ

 

📌 풀이 )

https://www.acmicpc.net/board/view/78670

글 읽기 - 혹시 저처럼 시간초과로 고생하시는 분들을 위해서..

위의 분의 힌트에서,, 답을 얻었다.(물론 한번에 맞진 못했음)

 

위의 bfs나 dfs로 풀 경우, 0인 칸들을 중복해서 탐색하게 된다.

Map을 한번만 훑는 것이 이 문제의 핵심이라고 볼 수 있다.

 

문제를 풀어보면 알겠지만, 0들끼리 묶여서 그룹이 될 수 있다.

만일 1을 기준으로 묶인 0그룹들이 다르다면, 1 벽을 부숨으로써 두 그룹 모두 방문이 가능하다.

예제 2

위와 같이 입력이 주어졌다고 가정하면,

 

위와 같이 그룹을 묶을 수 있다.

그룹을 저장하기 위하여 각 그룹별 고유 번호와 포함된 0의 개수를 저장하는 리스트를 나누었다.

 

group_cnt에는 그룹의 번호, group에는 그룹별 0의 개수를 저장한다.

group_cnt를 2부터 시작하고 group을 [0,0]으로 준 이유는 Map에 바로 group 고유 번호를 저장하고 싶은데, 0과 1은 이미 있기 때문이다.

 

즉 Map에는 위와 같이 저장되고 group에는 해당 그룹별 0의 개수가 저장된다.

 

이제 이 값들을 가지고 출력을 해주어야한다.

방법은 위에서 언급한 바와 같이 1 주변 다른 그룹들의 합을 더해준다.

 

예를 들어 저 1을 기준으로 생각하면, 해당 벽이 부숴지면 3번 그룹, 4번 그룹, 6번 그룹 모두 방문가능하다.

그러므로 3번그룹의 0의 개수 3개, 4번 그룹 0의 개수 1개, 6번 그룹 0의 개수 1개를 전부 더해준다.

 

(여기서 문제에는 명확하게 나오진 않았지만, 예제를 통해 벽을 부수고 생긴 영역(?)도 이동 가능한 칸으로 세어주는 듯 했다. 그래서 주변 그룹들의 값 + 현재위치로 계산했다.)

 

만일 Map의 값이 1보다 크면, 원래 이동가능했던 칸이므로 0을 출력해준다.

 

 

 

+)

다 풀고, visit 선언을 bfs안에 넣어줬다가 시간초과가 났다.
visit을 밖으로 빼주는 것 만으로 통과하긴 했지만, visit을 어디서 점검하냐에 따라 시간이 줄었다.
아래는 가장 시간이 짧았던 코드이다.

 

 

# 벽 부수고 이동하기 4
from collections import deque

N, M = map(int,input().split())
Map = [list(map(int, input())) for _ in range(N)]
group_cnt = 2
group = [0,0]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
visit = list([True]*M for _ in range(N))

def bfs(sx, sy):    
    queue = deque([[sx,sy]])    
    count = 0
    
    while queue :
        x, y = queue.popleft()
        count += 1
        Map[x][y] = group_cnt
        for i in range(4):
            ix = x + dx[i]
            iy = y + dy[i]
            if N > ix >= 0 and M > iy >= 0 and Map[ix][iy] == 0 and visit[ix][iy] == True:
                queue.append([ix,iy])
                visit[ix][iy] = False
    return count

for i in range(N):
    for j in range(M):
        if Map[i][j] == 0 : # 그룹 생성
            visit[i][j] = True
            group.append(bfs(i,j))
            group_cnt += 1
            
for x in range(N) :
    for y in range(M):
        near_list = set()
        tmp = 1
        if Map[x][y] > 1 :
            print(0,end='')
        else :
            for i in range(4):
                ix = x + dx[i]
                iy = y + dy[i]
                if N > ix >= 0 and M > iy >= 0 and Map[ix][iy] not in near_list:
                    near_list.add(Map[ix][iy])
                    tmp += group[Map[ix][iy]]
            print((tmp)%10, end='')
    print()