import sys
N = int(sys.stdin.readline())
land = list()
for _ in range(N):
land.append(list(map(int, sys.stdin.readline().split())))
max_result = 0
for height in range(101):
result = 0
visited = [[False for _ in range(N)] for _ in range(N)]
for i in range(N):
for t in range(N):
if visited[i][t] is False and land[i][t] > height:
visited[i][t] = True
need_visit = [[i, t]]
result += 1
while need_visit:
cur_i, cur_t = need_visit.pop()
for next_i, next_t in [[cur_i + 1, cur_t], [cur_i - 1, cur_t], [cur_i, cur_t + 1], [cur_i, cur_t - 1]]:
if 0 <= next_i < N and 0 <= next_t < N and not visited[next_i][next_t] and land[next_i][next_t] > height:
need_visit.append([next_i, next_t])
visited[next_i][next_t] = True
max_result = max(max_result, result)
print(max_result)
import sys
for _ in range(int(sys.stdin.readline().strip())):
M, N, K = map(int, sys.stdin.readline().split())
land = [[0 for _ in range(M)] for _ in range(N)]
for _ in range(K):
m, n = map(int, sys.stdin.readline().split())
land[n][m] = 1
result = 0
visited = [[False for _ in range(M)] for _ in range(N)]
for n in range(N):
for m in range(M):
if visited[n][m] or land[n][m] == 0:
continue
result += 1
need_visit = [[n, m]]
visited[n][m] = False
while need_visit:
cur_n, cur_m = need_visit.pop()
for next_n, next_m in [[cur_n, cur_m + 1], [cur_n, cur_m - 1], [cur_n + 1, cur_m], [cur_n - 1, cur_m]]:
if 0 <= next_n < N and 0 <= next_m < M:
if land[next_n][next_m] == 1 and visited[next_n][next_m] is False:
need_visit.append([next_n, next_m])
visited[next_n][next_m] = True
print(result)
visited 배열을 만들어 방문했던 기록을 남기고, 만약 방문했던 곳이라면 해당 지역은 건너뛸 수 있도록 했다.
그리고 항상 그래프를 탐색할 때에는 구역 내에 있는 지 확인을 먼저 하고 진행할 수 있도록 했다.
만약 땅이 맞다면, 방문을 한다는 의미로 visited를 True로 바꾸고 다음에 방문을 진행할 need_visit 배열에 추가하도록 했다.
import sys
dx = [0, 1, 1, 1, 0, -1, -1, -1]
dy = [-1, 0, 1, -1, 1, 0, -1, 1]
while True:
w, h = map(int, sys.stdin.readline().split())
if w == 0 and h == 0:
break
land = list()
visited = [[False for _ in range(w)] for _ in range(h)]
result = 0
for _ in range(h):
land.append(list(map(int, sys.stdin.readline().split())))
for height in range(h):
for width in range(w):
if visited[height][width] is True:
continue
if land[height][width] == 0:
visited[height][width] = True
continue
result += 1
need_visit = [[height, width]]
visited[height][width] = True
while need_visit:
cur_height, cur_width = need_visit.pop(0)
for i in range(8):
target_height, target_width = cur_height + dy[i], cur_width + dx[i]
if 0 <= target_height < h and 0 <= target_width < w and land[target_height][target_width] == 1 and not visited[target_height][target_width]:
need_visit.append([target_height, target_width])
visited[target_height][target_width] = True
print(result)
import sys
N, M = map(int, sys.stdin.readline().split())
miro = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
visited = [[float('inf') for _ in range(M)] for _ in range(N)]
bfs = [[0, 0, 0]]
result = -1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while bfs:
count, x, y = bfs.pop(0)
if x == N - 1 and y == M - 1:
result = count
break
for i in range(4):
if 0 <= x + dx[i] < N and 0 <= y + dy[i] < M and miro[x + dx[i]][y + dy[i]] == 1 and visited[x + dx[i]][y + dy[i]] > count + 1:
bfs.append([count + 1, x + dx[i], y + dy[i]])
visited[x + dx[i]][y + dy[i]] = count + 1
print(result + 1)
입력받은 edge를 배열에 저장하고 해당 배열을 DFS, BFS에 맞게 탐색하면서 풀었다.
DFS, BFS에서의 다른 점은 BFS는 바로바로 다음 방문 배열에 넣은 반면, DFS는 해당 노드에서 인접한 노드를 모두 구해 배열로 만든 후 다음 방문 배열 앞으로 넣어주었다.
import sys
N, M, V = map(int, sys.stdin.readline().split())
graph = [[False for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
V1, V2 = map(int, sys.stdin.readline().split())
graph[V1-1][V2-1] = True
graph[V2-1][V1-1] = True
DFS, BFS = [False for i in range(N)], [False for i in range(N)]
to_visit = [V-1]
while to_visit:
cur_node = to_visit.pop(0)
if DFS[cur_node]:
continue
save_to_visit = []
for i in range(N):
if graph[cur_node][i] and not DFS[i]:
save_to_visit.append(i)
to_visit = save_to_visit + to_visit
print(cur_node + 1, end=' ')
DFS[cur_node] = True
print()
to_visit = [V-1]
while to_visit:
cur_node = to_visit.pop(0)
if BFS[cur_node]:
continue
for i in range(N):
if graph[cur_node][i] and not BFS[i]:
to_visit.append(i)
print(cur_node + 1, end=' ')
BFS[cur_node] = True
