https://www.acmicpc.net/problem/2667
문제 설명에 나와있는 것을 보면....
2차원 행렬을 그래프로 표현해 BFS나 DFS로 순회한다? 설명이 뭔가 난해했다.
2차원 행렬을 그래프로 표현해? 2차원 행렬은 인접 노드들을 표현하기 위한 거였는데...
여기에 낚이지 말자. BFS나 DFS에서 썼던 2차원 행렬은 대각선으로 접었을 때 똑같은 데칼코마니 행렬이고,
여기서 말하는 2차원 행렬은 그냥 집이 있음/없음을 나타내는 불규칙한 행렬이다. 이걸 BFS나 DFS로 순회해보자는 거다.
자, 그럼 인접한 노드들은 어떻게 알 수 있을까?
인덱스로 알 수 있다. 어떤 한 집의 주소가 houses[row][col] 이라면, 인접한 집은 위/아래/왼쪽/오른쪽이므로
이웃집들은 [row+1, col], [row-1, col], [row, col-1], [row, col+1] 이다. 인접 노드들은 이것들로 잡으면 된다.
하지만 이 이웃집들이 항상 존재하는 것은 아니다.
집이 없을수도 있고 (houses[row][col] == 0),
땅조차 없을 수도 있다. (row나 col이 mapSize를 벗어날 때)
이러한 조건들을 맞춰주면서 BFS나 DFS를 짜면 된다.
데이터 입력부
import sys
mapSize = int(sys.stdin.readline())
houses = [sys.stdin.readline()[:-1] for _ in range(mapSize)] # 입력
visited = [[0 for _ in range(mapSize)] for _ in range(mapSize)] # 이미 카운트됨 표시
ret = []
for row in range(mapSize):
for col in range(mapSize):
if houses[row][col] == '1' and visited[row][col] == 0:
newTown = BFS(row, col) # 리스트에 값이 추가될 때마다 새로운 단지 추가
ret.append(newTown) # newTown에 저장된 숫자는 각 단지에 포함된 가구 수mapSize는 한 변의 길이이다. houses는 입력받은 1010111...따위를 저장한 리스트고,
visited는 이미 카운트된 집을 표시하는 리스트이다. DFS나 BFS에서 사용하는 이름을 그냥 따왔다. 어떤 조사원 한 명이 집집마다 방문하면서 단지 수를 센다고 생각하면 이해하기 편하겠다.
7번 줄부터 이중 for문을 돌면서 houses가 1인 곳을 찾는데, mapSize가 최대 25이므로 0부터 제일 끝까지 살펴봤자 25*25=625밖에 안된다. 맘편하게 돌자.
참고로 제출할 때는 4번 줄에 [:-1]을 없애야 한다. 백준 데이터 입력은 스트링 맨 끝에 \n 없이 들어오기 때문이다.
테스트 케이스를 복붙할 때는 \n이 있어서 코딩할 때는 저렇게 해야지 어쩔 수 없다.
DFS (스택)
def DFS(row, col):
stack = [] # houses가 1인 이웃집들이 추가될 것임
stack.append([row, col])
connected = 0 # 가구 수
while stack:
[r, c] = stack.pop()
if visited[r][c] == 0:
connected += 1
visited[r][c] = 1
for [nR, nC] in [[r+1, c], [r-1, c], [r, c+1], [r, c-1]]: # 인접
if 0 <= nR < mapSize and 0 <= nC < mapSize: # 범위 체크
if houses[nR][nC] == '1':
stack.append([nR, nC])
return connected
print(len(ret))
ret.sort()
for i in ret:
print(i)houses가 1인 이웃집들만 스택에 추가를 해 주면서, 아직 방문하지 않았다면 connected에 하나 추가하는 식으로 가구 수를 세어 나가면 된다.
BFS
import collections
def BFS(row, col):
queue = collections.deque() # houses가 1인 이웃집들이 추가될 것임
queue.append([row, col])
connected = 0 # 가구 수
while queue:
[r, c] = queue.popleft() # 큐에서 꺼낸 row, col -> r, c
if visited[r][c] == 0:
connected += 1
visited[r][c] = 1
for [nR, nC] in [[r+1, c], [r-1, c], [r, c+1], [r, c-1]]: # 인접.이웃.
if 0 <= nR < mapSize and 0 <= nC < mapSize: # 범위 체크
if houses[nR][nC] == '1':
queue.append([nR, nC])
return connected
print(len(ret))
ret.sort()
for i in ret:
print(i)BFS도 똑같으니 설명 생략.
'알고리즘 > BFS와 DFS' 카테고리의 다른 글
| 2206번. 벽 부수고 이동하기 (0) | 2019.12.18 |
|---|---|
| 7576번. 토마토 (0) | 2019.12.17 |
| 1012번. 유기농 배추 (0) | 2019.12.13 |
| 2606번. 바이러스 (0) | 2019.12.13 |
| 1260번. DFS와 BFS (0) | 2019.12.13 |