[Baekjoon] 2468. 안전 영역

문제 링크

https://www.acmicpc.net/problem/2468

문제 해석

• 2차원 배열의 크기를 정하는 n 제공 ( 2<= n <= 100)
• 높이를 의미하는 2차원 배열 제공 ( 1<= 높이 <= 100)

문제 해결

• 잠기지 않은 지점을 발견할 시 , 주변 을 다 순회 ( 동 서 남 북 )
• 이미 방문이 된 곳일 시 , return
• 다 순회 한 후 엔 다시 반복문 돌며 , 잠기지 않은 지점 탐색

슈도 코드

dfs(x,y):
	if ( x <0 또는 x >= n ) 또는 ( y<0 또는 y>= n)
		return
	if visited[x][y] ==True
		return
	ary[x][y]-min<=0
		return
	visited[x][y] = True
	dfs(x-1,y,min)
	dfs(x+1,y,min)
	dfs(x,y+1,min)
	dfs(x,y-1,min)
for min 0~101
	count =0 
	for i 0~n
		for j 0~n
		
			if visited[i][j] False and ary[i][j]>0
				dfs(x,y,min)
				count+=1
	if count == 0
		break
	if max_result <count
		max_result = count
print(max_result)

제출 코드

import sys
n = int(input())
ary = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
sys.setrecursionlimit(15000)
max_result = 0
def dfs(x,y,min):
    if x == -1 or y == -1 or x ==len(ary) or y==len(ary):
        return
    if ary[x][y] -min<=0:
        return
    if visited[x][y] == True:
        return
    visited[x][y] = True
    dfs(x-1,y,min)
    dfs(x+1,y,min)
    dfs(x,y+1,min)
    dfs(x,y-1,min)
min = 0
for min in range(101):
    count = 0
    visited = [[False for j in range(n)] for i in range(n)]
    for i in range(n):
        for j in range(n):
            if visited[i][j] == False and ary[i][j]-min>0:
                
                dfs(i,j,min)
                count +=1
    if(count == 0):
        break
    if count>max_result:
        max_result = count


print(max_result)

사담

• 초등부 2번 문제인데 , 애들이 dfs 나 bfs 이론을 알고 있는지 참 궁금하다
• 동서남북 순회 하고 , 중복이 안되게 하는 법 만 알면 풀 수는 있는 문제

Writed By Obisidan