2468번: 안전 영역

 

 

 

 

 

풀이

 

brute force,dfs,bfs로 풀 수 있는 문제입니다.

 

문제의 핵심은 물에 잠기지 않는 안전한 영역의 최대 개수를 출력 하는것입니다.

 

 

 

 

 

dfs

...

1부터 graph의 최대 숫자 값까지 반복문을 돌립니다.

 

(아직 방문하지 않은 영역) visited[i][j]의 값이 k보다 크다면 dfs를 호출하고 visited[x][y] = k로 방문처리 해줍니다.

 

nx,ny로 다음 위치를 특정해주고 (아직 방문하지 않은 영역) visited[nx][ny]의 값이 k보다 크다면 dfs를 재호출 하고 방문처리 합니다.

 

dfs함수가 종료될때마다 물에 잠기지 않은 영역을 모두 탐색한것 이므로 cnt의 값을 1증가 시켜줍니다.

 

마지막으로 물에 잠기지 않는 안전한 영역의 최대 개수를 출력합니다.

...

 

 

 

 

bfs

...

1부터 graph의 최대 숫자 값까지 반복문을 돌립니다.

 

(아직 방문하지 않은 영역) visited[i][j]의 값이 k보다 크다면 visited[i][j] = k로 방문처리 하고 bfs를 호출합니다.

 

nx,ny로 다음 위치를 특정해주고 (아직 방문하지 않은 영역) visited[nx][ny]의 값이 k보다 크다면 queue에 nx,ny값을 넣고 방문 처리 합니다.

 

queue가 비게 되면 물에 잠기지 않은 영역을 모두 탐색한것 이므로 cnt의 값을 1증가 시켜줍니다.

 

마지막으로 물에 잠기지 않는 안전한 영역의 최대 개수를 출력합니다.

...

 

 

 

 

 

 

 

파이썬 dfs

from sys import stdin
import sys
sys.setrecursionlimit(3000000)

def dfs(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    visited[x][y] = k

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] > k:
            dfs(nx, ny)
            
n = int(input())

graph = [list(map(int, stdin.readline().split())) for _ in range(n)]

maxCnt = 1
for k in range(1, max(map(max, graph))+1):
    visited = [item[:] for item in graph]
    cnt = 0

    for i in range(n):
        for j in range(n):
            if visited[i][j] > k:                
                dfs(i, j)
                cnt += 1

    maxCnt = max(maxCnt, cnt)
print(maxCnt)

 

 

 

 

 

파이썬 bfs

from collections import deque
from sys import stdin

def bfs(x, y):
    dx = [1, -1, 0, 0]
    dy = [0, 0, -1, 1]

    queue = deque()
    queue.append((x,y))

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] > k:
                visited[nx][ny] = k
                queue.append((nx, ny))

n = int(input())
graph = [list(map(int, stdin.readline().split())) for _ in range(n)]

maxCnt = 1
for k in range(1, max(map(max, graph))+1):
    visited = [item[:] for item in graph]
    cnt = 0

    for i in range(n):
        for j in range(n):
            if visited[i][j] > k:
                visited[i][j] = k
                bfs(i, j)
                cnt += 1
                
    maxCnt = max(maxCnt, cnt)
print(maxCnt)