3 분 소요

[공지사항] [‘코딩테스트 필수 알고리즘’ 강의를 듣고 이해한 내용을 바탕으로 직접 필기한 내용입니다. ] 👉🏻바로가기



그래프Permalink

  • BFS : Breadth-first search (너비 우선 선택)
  • DFS : Depth_first search(깊이 우선 선택)



BFSPermalink

1. 아이디어Permalink

  • 시작점에 연결된 vertex 찾기
  • 찾은 vertex를 queue에 저장
  • queue의 가장 먼저 것을 뽑아서 반복

큐란 무엇이나 선입선출 먼저들어온것이 먼저 나감.

BFS 그래프에서 큐를 쓰는 이유? 12345 넣었을때 1확인하면 1이 나가야함.

스택 선입후출-DFS



2. 시간복잡도Permalink

BFS : O(V+E)



3. 자료구조Permalink

  • 검색할 그래프
  • 방문여부 확인(재방문 금지)
  • Queue : BFS 실행.



BFS 기본예제 : 백준 1926Permalink

2중 For 문에서는 값이 1이, 방문 x

아이디어

  • 2중 for문, 값이 1 && 방문 X → BFS

  • BFS돌면서 그림 개수 +1, 최댓값을 갱신


시간복잡도

  • BFS : O(V+E)

  • V : M*N

  • E : V * 4

O(V+E) = V + 4V = 5V

M = 500, N = 500

MN = 250000*5 = 1250000

100만 < 2억 > 가능!


자료구조

  • 그래프 전체 지도 : int[][]

  • 방문 : bool[][]

  • queue : bfs



import sys

input = sys.stdin.readline

n,m = map(int, input().split())
map = [list(map(int, input().split()) for _ in range(n)] #n(세로)_에 대해서 M개의 데이터가 들어옴. 
chk = [[False] * m for _ in range(n)]

cnt = 0
maxv = 0

dy = [0,1,0,-1]
dx = [1,0,-1,0]

def bfs(y,x):
	rs = 1
	q = [(y,x)]
	while q:
		ey, ex = q.pop()
		for k in range (4):
			ny = ey + dy[k]
			nx = ex + dx[k] #현재 위치에서 다음위치 좌표 계산)
			if 0<=ny<n and 0<=nx<m: #조건에 맞는지 확인
				if map[ny][nx] == 1 and chk[ny][nx] == False:
					rs += 1 
					chk[ny][nx] = True
					q.append((ny,nx))
		return rs
	

for j in range(n):
	for i in range(m):
		if map[j][i] == 1 and chk[j][i] == False:
			chk[j][i] = True
			#전체 그림 갯수를 +1
			cnt = cnt + 1
			# BFS 를 통해 그림의 크기를 구해주고
			maxv = max(maxv, bfs(j,i))
			# BFS 결과를 최댓값 갱신.

print(cnt)
print(maxv)



DFSPermalink

DFS : Depth-first search(깊이 우선 선택) 자식 노드 우선 탐색 즉 스택 또는 재귀함수를 사용.

그래프 탐색은 사실 BFS 로 가능

  • 연결되어 있는 그래프를 구현 할 수 있기 때문

DFS의 사용 이유는? 재귀 함수를 통해 백트래킹 을 구현하기 위해



재귀함수Permalink

  • 자기 자신을 다시 호출하는 함수
  • 주위할점
    • 재귀 함수가 종료되는 시점 반드시 명시
    • 재귀함수의 깊이가 너무 깊어지면 Stack Overflow
  • DFS, 백트래킹에서 주로 사용.



아이디어Permalink

  • 시작점에 연결된 Vertex 찾기
  • 연결된 Vertex를 계속해서 찾음(끝날 때 까지)
  • 더이상 연결된 Vertex가 없을 경우 다음



시간복잡도Permalink

  • DFS : O(V+E)



자료구조Permalink

  • 검색할 그래프 : 2차원 배열
  • 방문여부 확인 : 2차원 배열(재방문 금지)



DFS 기본문제 : 백준 2667Permalink

  • 2중 for문, 1, 방문여부 확인 ⇒ 재귀(DFS)

아이디어

  • 2중 for, 값 1 && 방문 x => DFS
  • DFS를 통해 찾은 값을 저장 후 정렬 해서 출력

시간복잡도

  • DFS : V + E
  • V, E : N^2, 4N^2
  • V + E : N^2 = 625 » 가능

자료구조

  • 그래프 저장 : int [][]
  • 방문여부 : bool[][]
  • 결과값 : int[]
import sys

input = sys.stdin.readline

N = int(input())
map = [list(map(int, input().strip())) for _ in range(N)]
chk = [[False] * N for _ in range(N)]

result = []
each = 0
dy = [0,1,0,-1]
dx = [1,0,-1,0]
# 시계반댓방향으로 돌때 y는 아래로 가는만큼 1, x는 오른쪽으로 가는만큼 1
(0,1)->(1,0)->(0,-1)->(-1,0)


def dfs(y,x):
  global each
  each += 1 #전역 변수 사용
  for k in range(4): #동서남북 찾기
    ny = y + dy[k]
    nx = x + dx[k]
    if 0<=ny<N and 0<=nx<N:
      if map[ny][nx] == 1 and chk[ny][nx] == False:
        chk[ny][nx] = True
        dfs(ny,nx)



for j in range(N):
  for i in range(N):
    if map[j][i] == 1 and chk[j][i] == False:
      chk[j][i] = True
    	# 방문 체크 표시
      each = 0
      dfs(j,i)
      result.append(each) 
      # DFS 로 크기 구하기
      # BFS : 함수 호출, 리턴값으로 크기를 받아옴, 하지만 재귀는 크기 받아오는게 어려움
      # 크기를 결과 리스트에 넣기

      
result.sort()
print(len(result))
for i in result:
  print(i)

댓글남기기

참고