백준 16946 벽 부수고 이동하기 4
문제
https://www.acmicpc.net/problem/16946
코드
from collections import deque
input = __import__('sys').stdin.readline
def bfs(y, x):
q = deque()
q.append((y, x))
temp[y][x] = num
cnt = 1
while q:
nowy, nowx = q.popleft()
for i in range(4):
newy = d[i][0]+nowy
newx = d[i][1]+nowx
if newy < 0 or newy >= n or newx < 0 or newx >= m or board[newy][newx] != 0 or temp[newy][newx] != 0:
continue
temp[newy][newx] = num
q.append((newy, newx))
cnt += 1
return cnt
n, m = map(int, input().split())
board = [list(map(int, input().strip())) for _ in range(n)]
temp = [[0]*m for _ in range(n)]
d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
cnts = {}
num = 1
for i in range(n):
for j in range(m):
if board[i][j] == 1 or temp[i][j] != 0:
continue
cnt = bfs(i, j)
cnts[num] = cnt
num += 1
for i in range(n):
for j in range(m):
if board[i][j] == 0:
continue
group_list = set()
for di in range(4):
newy = d[di][0]+i
newx = d[di][1]+j
if newy < 0 or newy >= n or newx < 0 or newx >= m or temp[newy][newx] == 0:
continue
group_list.add(temp[newy][newx])
for k in group_list:
board[i][j] += cnts[k]
board[i][j] %= 10
result = ''
for i in board:
result += ''.join(map(str, i))+'\n'
print(result)
풀이
dfs,bfs를 사용한 풀이
가장 처음 접근은 dfs를 사용했습니다 현재 좌표값이 1일 경우 dfs를 통해서 연결되어 있는 0값들을 카운팅해서 board[i][j]를 수정했습니다 정답은 맞았는데 시간초과가 떴구요 구글에 검색해서 풀이법을 찾아봤습니다
시간을 단축하기 위해 0이 연속적으로 있는 구역들을 그룹핑해서 저장 후 카운팅
bfs를 통해 0의 범위들에게 그룹번호를 지정해줍니다 예를 들어 문제 2번 예시인
4 5
11001
00111
01010
10101
입력이 들어 왔을 경우 temp는
00110
22000
20304
05060
이렇게 저장이 되는데 저 구역의 번호를 저장해논거에요
그리고 그룹번호를 인덱스로 리스트나 딕셔너리를 만들어서 구역의 크기를 저장해줍니다
print(list) #[0,2,3,1,1,1,1]
이런식으로 나오겠네요 1번 그룹의 0의 개수는 2개, 2번 그룹의 0의 개수는 3개~~
그 후에 board를 순회돌면서 4방향의 그룹번호에 해당하는 값을 더해주면 됩니다
후기
bfs 함수를 잘못 설계해서 2시간동안 문제를 찾았네요 이번 문제처럼 영역을 찾는 알고리즘을 플러드 필이라고 부른다고 합니다 영역을 그룹핑해서 시간을 단축시키는 방법은 아마 혼자서는 생각하지 못했을 거 같아요
2시간동안 힘들었지만 그래도 많이 배운거같아서 뿌듯합니다 하하
Author And Source
이 문제에 관하여(백준 16946 벽 부수고 이동하기 4), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@josajang98/백준-16946-벽-부수고-이동하기-4저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)