[Python] 백준 2468번 : 안전 영역 (S1) - DFS&BFS 필수문제3

#문제

www.acmicpc.net/problem/2468

2468번: 안전 영역

#풀이 & 학습한 내용

DFS 또는 BFS로 구분되는 영역의 최대 갯수를 구하는 문제입니다.

 

#소스코드

from collections import deque #큐 사용하기 위해

dx=[0,0,1,-1]
dy=[1,-1,0,0] #상하좌우

def bfs(q): #bfs로 경로있는 vertex들 모두 방문처리
  while q:
    v=q.popleft()
    now_x=v[0]
    now_y=v[1] #큐에서 뽑은 vertex의 x,y좌표

    for k in range(4): #상하좌우방향
      new_x=now_x+dx[k]
      new_y=now_y+dy[k]

      if (0<=new_x<N) and (0<=new_y<N): #범위 벗어나지 않고
        if areas[new_x][new_y]>water_height and not visited[new_x][new_y]: #안전영역이면서 방문 안한 경우
          visited[new_x][new_y]=True #방문처리
          q.append([new_x,new_y]) #다음 인접한 vertex들을 살피기 위해 큐에 넣기


N=int(input())
areas=[list(map(int,input().split())) for _ in range(N)] #N*N 2차원 리스트 입력받기
max_num=-1 #답인 최대 개수 저장시킬 변수

for water_height in range(0,101): #몇층까지 잠기는지 0~100 순서대로
  count=0 #이 때의 안전영역 수 저장시킬 변수
  visited=[[False]*N for _ in range(N)] #이때의 방문여부 확인하기 위한 리스트

  for i in range(0,N):
    for j in range(0,N): #모든 지역에 대해
      if areas[i][j]>water_height and not visited[i][j]: #안전영역이면서 방문 안한 경우(새로운 구분되는 곳)
        count+=1
        visited[i][j]=True 
        q=deque([[i,j]]) #방문처리해주고 큐에 넣기
        bfs(q) #경로있는 vertex들 모두 방문처리해준다

  if count > max_num:
    max_num=count

print(max_num)

github.com/HoYoungChun/Algorithm_PS/blob/master/DFS%26BFS/BOJ_2468.py

HoYoungChun/Algorithm_PS

※ 20210314 풀이

dfs와 bfs 모두 코드로 편하게 구현할 수 있어야 합니다.

import sys
sys.setrecursionlimit(10**6) #dfs에서 재귀깊이 늘리기
input=sys.stdin.readline #시간초과 방지
from collections import deque #bfs에서 큐 쓰기위해

dx=[0,0,1,-1]
dy=[1,-1,0,0] #상하좌우 for문 위해

def dfs(now_x,now_y):
  visited[now_x][now_y]=True #방문처리

  for i in range(4):
      new_x,new_y=now_x+dx[i],now_y+dy[i] #상하좌우 방향의 새로운 x,y좌표
      if (0<=new_x<N) and (0<=new_y<N): #범위안에 있고
        if maps[new_x][new_y]>rain_h and not visited[new_x][new_y]: #잠기지않고 방문한 적 없을때
          dfs(new_x,new_y)

def bfs(q):
  while q: #경로있는애들 다 방문할때까지
    now_x,now_y=q.popleft() #큐에서뽑은거의 x,y좌표

    for i in range(4):
      new_x,new_y=now_x+dx[i],now_y+dy[i] #상하좌우 방향의 새로운 x,y좌표
      if (0<=new_x<N) and (0<=new_y<N): #범위안에 있고
        if maps[new_x][new_y]>rain_h and not visited[new_x][new_y]: #잠기지않고 방문한 적 없을때
          visited[new_x][new_y]=True #방문처리
          q.append([new_x,new_y]) #큐에 넣어서 인접한 곳 살피기


N=int(input()) #가로 세로 크기 
maps=[list(map(int,input().split())) for _ in range(N)] #높이 정보

max_count=-1 #안전영역 최대개수

for rain_h in range(0,100): #비의 높이
  now_count=0 #안전영역 개수 세는 변수
  visited = [[False]*N for _ in range(N)] #방문여부
  for i in range(N):
    for j in range(N):
      if maps[i][j]>rain_h and not visited[i][j]: #잠기지않고 방문한적없을때
        now_count+=1 #안전영역 1증가
        #visited[i][j]=True #방문처리
        #q=deque([[i,j]]) #큐에 넣기 [x좌표,y좌표]
        #bfs(q) #bfs로 인접한 안전영역 방문처리
        dfs(i,j)
  
  max_count=max(max_count,now_count) #안전영역 최대개수 갱신

print(max_count)

github.com/HoYoungChun/Algorithm_PS/blob/master/DFS%26BFS/BOJ_2468_2.py

HoYoungChun/Algorithm_PS