[파이썬] 백준 16946 : 벽 부수고 이동하기 4 (골드2)

[파이썬] 백준 16946 : 벽 부수고 이동하기 4 (골드2)

 

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

---

문제

---

풀이

0. 방향성 생각

• DFS로 0으로 연결된 군집 사이즈 구하기.
• 1을 0으로 바꿨을 때 주변에 연결된 군집 크기와 더해주기.
• 상하좌우에서 4방향 탐색 시 같은 군집을 여러번 셀 수 있으니 중복처리 해주기.

1. 입력

import sys
sys.setrecursionlimit(10**6)
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(map(int,list(input()))) for _ in range(h)]
visit = [[0]*w for _ in range(h)]

입력을 받고 방문처리를 위한 VISIT 배열 만들어주기.

 

2. DFS 함수 정의

def dfs(x,y):
    global temp,count
    if x<0 or y<0 or x>=w or y>=h :
        return 0
    if arr[y][x] == 0 and not visit[y][x]:
        temp.add((x,y))
        visit[y][x] = count
        return 1+dfs(x-1,y)+dfs(x+1,y)+dfs(x,y-1)+dfs(x,y+1)
    return 0

DFS 정의

arr 값이 0이고, 방문하지 않은 지점일 때 탐색.

이 때 temp는 0으로 연결된 모든 지점의 좌표들을 임시로 저장할 set.

군집에는 방문처리를 하면서 번호 count를 매겨준다.

 

3. 탐색

info = {}
count = 1
for i in range(h):
    for j in range(w):
        if arr[i][j] == 0 and not visit[i][j]:
            temp = set()
            dfs(j,i)
            size = len(temp)
            count += 1
            for nx,ny in temp:
                info[(nx,ny)] = size

0인 지점에서 방문하지 않았으면 탐색시작.

temp에 연결좌표를 모두 넣고, 군집 크기는 temp의 크기로 지정.

군집 탐색이 끝났으면 다음 군집 번호를 매기기 위해 count += 1

딕셔너리로 모든 좌표에 size를 지정해준다.

 

4. 벽 부수기

step = [[1,-1,0,0],[0,0,1,-1]]
for i in range(h):
    for j in range(w):
        if arr[i][j] == 1:
            size = 1
            visit_set = set()
            for s in range(4):
                nj = j + step[0][s]
                ni = i + step[1][s]
                if 0<=nj<w and 0<=ni<h and (nj,ni) in info:
                    if visit[ni][nj] not in visit_set:
                        visit_set.add(visit[ni][nj])
                        size += info[(nj,ni)]
            arr[i][j] = size

벽을 부수면서 4방향 탐색.

군집 중복방문을 처리하기 위한 visit_set

처음 방문하는 군집인 경우에만 size를 세주고 arr값을 변경한다.

 

5. 출력

for row in arr:
    s = ''
    for val in row:
        s += str(val%10)
    print(s)

10으로 나눈 나머지로 변경.

 

---

전체코드

import sys
sys.setrecursionlimit(10**6)
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(map(int,list(input()))) for _ in range(h)]
visit = [[0]*w for _ in range(h)]

def dfs(x,y):
    global temp,count
    if x<0 or y<0 or x>=w or y>=h :
        return 0
    if arr[y][x] == 0 and not visit[y][x]:
        temp.add((x,y))
        visit[y][x] = count
        return 1+dfs(x-1,y)+dfs(x+1,y)+dfs(x,y-1)+dfs(x,y+1)
    return 0

info = {}
count = 1
for i in range(h):
    for j in range(w):
        if arr[i][j] == 0 and not visit[i][j]:
            temp = set()
            dfs(j,i)
            size = len(temp)
            count += 1
            for nx,ny in temp:
                info[(nx,ny)] = size

step = [[1,-1,0,0],[0,0,1,-1]]
for i in range(h):
    for j in range(w):
        if arr[i][j] == 1:
            size = 1
            visit_set = set()
            for s in range(4):
                nj = j + step[0][s]
                ni = i + step[1][s]
                if 0<=nj<w and 0<=ni<h and (nj,ni) in info:
                    if visit[ni][nj] not in visit_set:
                        visit_set.add(visit[ni][nj])
                        size += info[(nj,ni)]
            arr[i][j] = size

for row in arr:
    s = ''
    for val in row:
        s += str(val%10)
    print(s)

 

코멘트

골2치고는 진짜 빨리풀었다.

효율성 점수 있었으면 info에 1과 연결된 부분만 넣는다든가, 벽 부수고 바로 10으로 나누면서 새 어레이 만든다드는 방식으로 시간 줄였을듯. (통과하긴 했는데)