백준 4963번
https://www.acmicpc.net/problem/4963
문제
후기
앞서 작성했던 유기농 배추 문제와 상당히 유사한 문제다. 단 이번에는 그와 달리
상하좌우가 아닌, 대각선으로도 이동할 수 있기 때문에, 이에 따른 방향만 구현해주면
되는 문제다. 그래프를 돌며 1을 만나면(땅을 만나면) 0으로 바꿔주고, 상하좌우 대각선을 탐색
한다. 인접한 땅은 같은 땅으로 count하여 최종 결과를 출력한다.
너비와 높이에 따른 그래프 선언을 항상 조심하자!!
나의 풀이
import sys
input= sys.stdin.readline
sys.setrecursionlimit(10**7)
# ↙ ← ↖ ↑ ↓ → ↘ ↗
dx = [-1,-1,-1, 0, 0, 1, 1,1]
dy = [-1, 0, 1, 1,-1, 0,-1,1]
def dfs(x,y):
if x<=-1 or x>=H or y<=-1 or y>=W:
return False
if graph[x][y] ==1: #땅이면
graph[x][y] = 0 #방문처리하고
for i in range(8): #상하좌우 대각선 탐색
nx = x+ dx[i]
ny = y + dy[i]
if nx <= -1 or nx>=H or ny<=-1 or ny>=W:
continue #맵을 넘어서면 DFS는 실행되지 않는다.
dfs(nx,ny)
return True
while True:
W, H =map(int,input().split())
result = 0
if W == 0 and H == 0: #0,0이면 종료
break
graph = []
for _ in range(H):
graph.append(list(map(int,input().split())))
for i in range(H):
for j in range(W):
if dfs(i,j)==True: #DFS 한번 순회할 때 마다 결과값 1 증가.
result+=1
print("{}".format(result))