DFS에서의 그래프 유형

1. 인접 행렬

# 변수 선언 및 입력
n, m = tuple(map(int, input().split()))

#index를 1번 부터 사용하기 위해 n+1만큼 할당합니다.
graph = [
    [0 for _ in range(n + 1)]
    for _ in range(n + 1)
]

visited = [False for _ in range(n + 1)]
vertex_cnt = 0

def dfs(vertex):
    global vertex_cnt
    
    # 해당 정점에서 이어져있는 모든 정점을 탐색해줍니다.
    for curr_v in range(1, n + 1):
        # 아직 간선이 존재하고 방문한 적이 없는 정점에 대해서만 탐색을 진행합니다.
        if graph[vertex][curr_v] and not visited[curr_v]:
            visited[curr_v] = True
            vertex_cnt += 1
            dfs(curr_v)
    

for i in range(m):
    v1, v2 = tuple(map(int, input().split()))

    # 각 정점이 서로 이동이 가능한 양방향 그래프이기 때문에
    # 각 정점에 대한 간선을 각각 저장해줍니다.
    graph[v1][v2] = 1
    graph[v2][v1] = 1

visited[1] = True
dfs(1)

print(vertex_cnt)

2. 인접 리스트

# 변수 선언 및 입력
n, m = tuple(map(int, input().split()))

#index를 1번 부터 사용하기 위해 m+1만큼 할당합니다.
graph = [[] for _ in range(n + 1)]

visited = [False for _ in range(n + 1)]
vertex_cnt = 0

def dfs(vertex):
    global vertex_cnt
    
    # 해당 정점에서 이어져있는 모든 정점을 탐색해줍니다.
    for curr_v in graph[vertex]:
        # 아직 간선이 존재하고 방문한 적이 없는 정점에 대해서만 탐색을 진행합니다.
        if not visited[curr_v]:
            visited[curr_v] = True
            vertex_cnt += 1
            dfs(curr_v)
    
    
for i in range(m):
    v1, v2 = tuple(map(int, input().split()))

    # 각 정점이 서로 이동이 가능한 양방향 그래프이기 때문에
    # 각 정점에 대한 간선을 각각 저장해줍니다.
    graph[v1].append(v2)
    graph[v2].append(v1)

visited[1] = True
dfs(1)

print(vertex_cnt)

인접 리스트와 인접 행렬의 차이점

for curr_v in graph[vertex]:
	if not visited[curr_v]:
		visited[curr_v] = True
		vertex_cnt += 1
		dfs(curr_v)

인접 리스트

for curr_v in range(1, n + 1):
	if graph[vertex][curr_v] and 
        not visited[curr_v]:
            visited[curr_v] = True
            vertex_cnt += 1
            dfs(curr_

인접 행렬

도달할 수 있는 정점의 수 구하기

import sys
import copy

## sys.exit() 디버깅 아예종료
## sys.maxsize = 정수 최대값

n,m = map(int,input().split())
graph = [
    list(map(int,input().split()))
    for i in range(n)
]

visited=[[0 for i in range(n)] for l in range(m)]

dxs, dys = [1,0], [0,1]

def can_go(x,y):
    print(x,y)
    if x<m and x>=0 and y<n and y>=0:
        return True
    if visited[x][y]==0:
        return False
    return False

cnt=0

def dfs(x,y):
		# dx, dy로 이동할 수 있는 방법 경우의 수 작성
    for dx, dy in zip(dxs,dys):
        dx, dy = x + dx, y + dy
        if dx<n and dx>=0 and dy<m and dy>=0:
            if graph[dx][dy]==1:
                graph[dx][dy]=0
                visited[dx][dy]=1
                dfs(dx,dy)
                
visited[0][0]=1
dfs(0,0)
if visited[-1][-1]==1:
    print(1)
else:
    print(0)

DFS (Stack)

• 최대한 깊게 탐색한 후 더이상 도달할 수 없는 상황이라면 이전으로 돌아가는 방식
  따라서 , 방문할 수 있는 지점이 있다면 방문하는 함수를 재귀호출. 더 이상 없다면 함수를 종료

→ 유의점은 방문했던 지점을 또 방문하면 효율이 떨어지므로 visited라는 배열을 만들어 이전에
방문 여부를 확인해야함

반드시 재귀함수를 이용하여 작성함

Heapq

• 가장 작은 두 숫자를 계속 빠르게 구해주기 위해 사용

import heapq

# 변수 선언 및 입력:
n = int(input())
arr = list(map(int, input().split()))

pq = []
ans = 0

# 우선순위 큐에 원소들을 전부 넣어줍니다.
# 작은 숫자 2개를 골라 합치는 것이 항상 유리함을 이용해야 하므로
# 작은 숫자가 먼저 골라질 수 있도록 해야합니다.
for elem in arr:
    heapq.heappush(pq, elem)

# 원소가 2개 이상이면 계속
# 가장 작은 숫자 2개를 골라
# 합치는 것을 반복합니다.
while len(pq) > 1:
    x1 = heapq.heappop(pq)
    x2 = heapq.heappop(pq)

    # 가장 작은 숫자 2개를 더하기 위한 비용을 답에 더해주고,
    # 두 숫자를 합친 결과를 우선순위 큐에 다시 넣어줍니다.
    ans += (x1 + x2)
    heapq.heappush(pq, x1 + x2)

print(ans)

묶음 내 특정 원소를 기준으로 정렬하는 방법

lst = [~~]
# N번째 원소 기준으로 오름차순 정렬시
lst.sort(key=lambda x:x[n-1]

# N번째 원소 기준으로 내림차순 정렬시
lst.sort(key=lambda x:x[n-1], reverse=True)

Lambda 란?

lambda a : b

• a : 입력 인자
• b: 입력 인자를 사용하여 계산할 값 즉, 계산하고 반환되는 값을 의미

특정 기준을 만족하는 배열 만들기

cmp_to_key(compare)

def compare(x, y):
    if x+y > y+x:
    	return -1
    elif x+y == y+x:
    	return 0
    else:
    	return 1

1. 양수 return → 두 input의 자리를 변경
2. 음수 return → 두 input의 자리 유지

두 가지 방안으로 사용 가능

arr.sort(key=cmp_to_key(compare))

arr = sorted(l, key=cmp_to_key(compare))

• Key란 정렬 조건을 의미함
  • 따라서 compare조건에 따른 정렬 조건을 임의로 만드는

동전 개수 최소로 구하기

$O(N)$

5원 동전 개수를 정하고 차액을 2로 나눌 수 있는지

MAX_NUM = n//5

for i in range(0, MAX_NUM + 1):
    remainder = n - 5 * i
    if remainder >= 0 and remainder % 2 == 0:
        ans = min(ans, i + (remainder // 2))

$O(N^2)$

5원 개수 최대치와 2원 개수 최대치를 모두 탐색

M = n//2
m = n//5

for i in range(m,0,-1):
    for l in range(M):
        if (i*5+l*2)==n:
            lst.append(l+i)

XOR

• arr[i] ^= 1은 arr[i]의 값이 0이면 1로, 1이면 0으로 바꾸는 작업을 수행

  • 두 비트가 같으면 0을 반환 (0 ^ 0 = 0, 1 ^ 1 = 0)

  • 두 비트가 다르면 1을 반환 (1 ^ 0 = 1, 0 ^ 1 = 1)

    1. sys

• sys.exit()

  • 함수 바로 종료

• sys.maxsize

  • 정수형 값중 최대값

2. 깔끔한 코드

• 최소값 리턴

if current > sub:
	current = sub
	
---------------------------------------------

current = min(current,sub)

• 배열에서 n개 원소 제외한 값의 경우의 수

# 총 합을 계산하고, 2중 for문을 통해 해당하는 원소만 골라서 합에서 빼주는 방

a = sum(list)
for i in range(len(list)):
	for l in range(i+1, n):
		del_2_param = a - list[i] - list[l]
		
---------------------------------------------		

# 나는 원소 한개 빼고 딥카피를 반복함 

for i in range(n):
    sub = copy.deepcopy(lst)
    del sub[i]
    for l in range(len(sub)):
        sub_2 = copy.deepcopy(sub)
        del sub_2[l]