BOJ:島の数[4963]
7353 ワード
1.質問
正方形からなる島と海洋地図を与える.島の個数を計算するプログラムを作成してください.
正方形が横、縦、または対角線に接続された長方形は、歩行可能な長方形です.
2つの正方形を同じ島にするには、1つの正方形から別の正方形まで歩く経路が必要です.地図は海に囲まれていて、地図を出すことができません.
ソース:https://www.acmicpc.net/problem/4963
2.アイデア
3.コード
mine# DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
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
# 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
dfs(x-1, y)
dfs(x, y-1)
dfs(x+1, y)
dfs(x, y+1)
dfs(x+1, y+1)
dfs(x+1, y-1)
dfs(x-1, y+1)
dfs(x-1, y-1)
return True
return False
while True:
w, h = map(int, input().split())
if w == 0 and h == 0:
break
graph = [list(map(int, input().split())) for _ in range(h)]
count = 0
for i in range(h):
for j in range(w):
# 현재 위치에서 DFS 수행
if dfs(i, j) == True:
count += 1
print(count)
Reference
この問題について(BOJ:島の数[4963]), 我々は、より多くの情報をここで見つけました
https://velog.io/@onejh96__/BOJ-섬의-개수-4963
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
# DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
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
# 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
dfs(x-1, y)
dfs(x, y-1)
dfs(x+1, y)
dfs(x, y+1)
dfs(x+1, y+1)
dfs(x+1, y-1)
dfs(x-1, y+1)
dfs(x-1, y-1)
return True
return False
while True:
w, h = map(int, input().split())
if w == 0 and h == 0:
break
graph = [list(map(int, input().split())) for _ in range(h)]
count = 0
for i in range(h):
for j in range(w):
# 현재 위치에서 DFS 수행
if dfs(i, j) == True:
count += 1
print(count)Reference
この問題について(BOJ:島の数[4963]), 我々は、より多くの情報をここで見つけました https://velog.io/@onejh96__/BOJ-섬의-개수-4963テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol