문제 링크
https://www.acmicpc.net/problem/4963
문제 유형
그래프 탐색 - DFS/BFS
🌈문제
정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.
한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.
두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.
둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.
입력의 마지막 줄에는 0이 두 개 주어진다.
출력
각 테스트 케이스에 대해서, 섬의 개수를 출력한다.
1. 첫 시도 + 아이디어
섬의 이어진 육지에 대한 자식들을 끝까지 탐색해야 한다. 섬에 이어진 육지들은 하나의 틀 취급을 받기 때문이다. 그렇기 때문에 DFS를 사용해야 한다는 것을 깨달았다. 내가 방문한 곳은 방문 처리를 해야 하며, 이차원 배열을 이용하여 각 값을 저장하고, 동서남북 그리고 대각선을 재귀함수로 돌아가면서 True값을 리턴하면 cnt를 하나 더해주고 False를 리턴하는 경우에는 cnt의 값을 더하지 않는 방식으로 풀이를 하려고 하였다.
2. 코드
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000) #재귀 제한을 걸어두지 않으면 runtype error 발생
def dfs(a,b):
if (a < 0) or (a >= h) or (b < 0) or (b >= w):
return False
if(island[a][b] == 1): #육지가 있는 지점이라면
island[a][b] = 0 #방문했다고 표현합니다.
dfs(a-1,b)
dfs(a,b-1)
dfs(a+1,b)
dfs(a,b+1)
dfs(a+1,b+1)
dfs(a-1,b+1)
dfs(a-1,b-1)
dfs(a+1,b-1)
return True
else:
return False
while(True):
w,h=map(int, input().split())
if(w==0) and (h==0): # 0 0 받으면 루프 종료합니다.
break
cnt = 0
island = [] # map초기화
for i in range(h):
island.append(list(map(int,input().split()))) #배열 입력받기
for i in range(h):
for j in range(w):
if dfs(i,j) == True:
cnt +=1
print(cnt)
처음 풀 때 시간초과가 나왔는데 재귀함수 제한 안걸어두었다...주의하기
이제 인덱스를 하나하나 방문하는 쪽으로 코드를 다시 짜보자. 재귀함수를 이용하지만 대각선 검사를 조금더 간단하게 하는 방법이다.
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000) #재귀 제한을 걸어두지 않으면 runtype error 발생
dx = [-1, 1, 0, 0, -1, -1, 1, 1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]
def dfs(a,b):
if(island[a][b] == 1):
island[a][b] = 0
for i in range(8):
na = a + dx[i]
nb = b + dy[i]
if na < 0 or na >= h or nb < 0 or nb >= w:
continue
if island[na][nb] == 0:
continue
if island[na][nb] == 1:
dfs(na,nb)
return True
else:
return False
while(True):
w,h=map(int, input().split())
if(w==0) and (h==0): # 0 0 받으면 루프 종료합니다.
break
cnt = 0
island = [] # island초기화
for i in range(h):
island.append(list(map(int,input().split()))) #배열 입력받기
for i in range(h):
for j in range(w):
if dfs(i,j) == True:
cnt +=1
print(cnt)+)사실 이 문제는 BFS로도 풀이가 가능하다
from collections import deque
dx = [-1, 1, 0, 0, -1, -1, 1, 1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]
def bfs(a,b):
queue = deque()
if (island[a][b] == 1):
island[a][b] = 0
queue.append((a,b)) #튜플을 담아요.
while queue: #큐가 빌 때까지
x,y = queue.popleft()
for i in range(8):
na = a + dx[i]
nb = b + dy[i]
if na < 0 or na >= h or nb < 0 or nb >= w:
continue
if island[na][nb] == 0:
continue
if island[na][nb] == 1:
island[a][b] = 0
queue.append((na,nb))
return True
else:
return False
while(True):
w,h=map(int, input().split())
if(w==0) and (h==0): # 0 0 받으면 루프 종료합니다.
break
cnt = 0
island = [] # island초기화
for i in range(h):
island.append(list(map(int,input().split()))) #배열 입력받기
for i in range(h):
for j in range(w):
if bfs(i,j) == True:
cnt +=1
print(cnt)이 친구는 끝까지 깊이 파고든다기 보다는 옆에 있는 아이들 먼저 보면서 간다는 마인드로 풀이해야 합니다.
