1. 문제 / 난이도 : Gold Ⅱ
16946번: 벽 부수고 이동하기 4
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이
www.acmicpc.net
2. 풀이 및 코드 설명
빠져나올 수 없는 시간 초과의 늪... + 10으로 나눈 나머지를 출력하라는 데 바보 같이 그냥 출력하고 있었음.
문제를 꼼꼼히 읽자...ㅎㅎ 처음에는 무작정 BFS로 짰다가 계속 시간초과가 나길래 (구글의 도움을 빌려서) 코드를 수정했다. 찾아보기로는 플러드 필이라는 알고리즘 구현을 요구하는 문제라고 한다. 처음 듣는 알고리즘이라 해당 알고리즘에 대해서는 나중에 별도로 정리해봐야겠다.
1. 인접해 있는 0을 묶어서 그룹 인덱스를 붙임
2. 해당 그룹에 0이 총 몇 개가 포함되어있는지를 저장하는 딕셔너리 생성
3. 보드를 돌 때마다 1을 만나면 상하좌우 그룹의 0 개수를 전부 더해서 출력(2번의 딕셔너리 이용)
위의 설명은 직관적으로 와닿지 않을 수도 있으니 아래 코드의 주석으로 자세히 설명하겠다.
(1) 초기화 및 설정
N, M = map(int, input().split())
board = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
visited = [[0 for _ in range(M)] for _ in range(N)]
zeros = [[0 for _ in range(M)] for _ in range(N)]- board : 전체 맵
- visited : BFS를 통해 이미 방문했는지, 아닌지 확인
- zeros : 인접한 0끼리 같은 그룹으로 묶어서 표시
(2) BFS - 그룹표시
group = 1
info = {}
for i in range(N):
for j in range(M):
if not board[i][j] and not visited[i][j]: #0인 칸이고 아직 방문하지 않은 노드이면
cnt = BFS(i, j) #BFS수행해서 인접한 0의 개수 리턴
info[group] = cnt #{index: cnt} 꼴로 삽입
group += 1 #그룹 인덱스 갱신- group : 그룹 인덱스
- info : {index: cnt} 형태의 딕셔너리. 각 그룹에 포함된 0의 개수 저장
- 아직 방문하지 않은 0인 칸마다 BFS수행해서 그룹 인덱스 표시해주고, 그룹별 0의 갯수 딕셔너리에 추가
def BFS(x, y):
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
q = deque()
q.append([x, y])
visited[x][y] = 1
cnt = 1
while q:
current_x, current_y = q.pop()
zeros[current_x][current_y] = group #그룹 인덱스 표시
for dx, dy in dir:
next_x, next_y = current_x + dx, current_y + dy
if next_x < 0 or next_y < 0 or next_x >= N or next_y >= M: continue
if visited[next_x][next_y]: continue
if not board[next_x][next_y]:
q.append([next_x, next_y])
visited[next_x][next_y] = 1
cnt += 1
return cnt
(3) 상하좌우 가능한 Move 개수 세기
answer = [[0 for _ in range(M)] for _ in range(N)]
for i in range(N):
for j in range(M):
if board[i][j]:
answer[i][j] = countMoves(i, j)def countMoves(x, y):
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)] #상하좌우 확인
candidates = set() #중복 제거 위해 set 사용
for dx, dy in dir:
next_x, next_y = x + dx, y + dy
if next_x < 0 or next_y < 0 or next_x >= N or next_y >= M: continue
if not zeros[next_x][next_y]: continue #그룹 인덱스가 0 = 보드값이 1
candidates.add(zeros[next_x][next_y]) #그룹 인덱스추가
cnt = 1
for c in candidates: #그룹들 전부 돌면서 cnt 더해주기
cnt += info[c]
cnt = cnt % 10 #10으로 나눈 나머지!
return cnt3. 전체 코드
import sys
from collections import deque
def BFS(x, y):
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
q = deque()
q.append([x, y])
visited[x][y] = 1
cnt = 1
while q:
current_x, current_y = q.pop()
zeros[current_x][current_y] = group
for dx, dy in dir:
next_x, next_y = current_x + dx, current_y + dy
if next_x < 0 or next_y < 0 or next_x >= N or next_y >= M: continue
if visited[next_x][next_y]: continue
if not board[next_x][next_y]:
q.append([next_x, next_y])
visited[next_x][next_y] = 1
cnt += 1
return cnt
def countMoves(x, y):
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
candidates = set()
for dx, dy in dir:
next_x, next_y = x + dx, y + dy
if next_x < 0 or next_y < 0 or next_x >= N or next_y >= M: continue
if not zeros[next_x][next_y]: continue
candidates.add(zeros[next_x][next_y])
cnt = 1
for c in candidates:
cnt += info[c]
cnt = cnt % 10
return cnt
N, M = map(int, input().split())
board = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
visited = [[0 for _ in range(M)] for _ in range(N)]
zeros = [[0 for _ in range(M)] for _ in range(N)]
group = 1
info = {}
for i in range(N):
for j in range(M):
if not board[i][j] and not visited[i][j]:
cnt = BFS(i, j)
info[group] = cnt
group += 1
answer = [[0 for _ in range(M)] for _ in range(N)]
for i in range(N):
for j in range(M):
if board[i][j]:
answer[i][j] = countMoves(i, j)
for i in range(N):
print(''.join(map(str, answer[i])))
'알고리즘 공부 > Baekjoon' 카테고리의 다른 글
| [백준 11062/Python] 카드 게임 (0) | 2020.11.12 |
|---|---|
| [백준 2668/C++] 숫자고르기 (0) | 2020.11.06 |
| [백준 2572/Python] 보드게임 (0) | 2020.10.25 |
| [백준 1092/Python] 배 (0) | 2020.10.24 |
| [백준 1058/C++] 친구 (0) | 2020.10.24 |
