해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 15651번 N과 M(3) - 백트래킹

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

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.

풀이

1. 백트래킹을 이용하여 풀 수 있는 문제입니다. 백트래킹의 가장 기초적인 문제라 할 수 있습니다. 15649의 문제에서 약간 변형된 문제입니다.

https://zidarn87.tistory.com/329

2. 중복을 허용하기 떄문에, for문에서 중복을 확인하는 if문이 삭제되었습니다.

전체 코드

N, M = map(int, input().split())
lst = []

def dfs(cnt):
    if cnt - 1 == M:  # 탈출 조건
        print(' '.join(map(str, lst)))
        return

    for i in range(1, N+1):
        lst.append(i)
        dfs(cnt+1)
        lst.pop()
dfs(1)

파이썬 / BOJ 백준 알고리즘 / 11724번 연결 요소의 개수 - DFS

문제 풀이 

이번 문제는 dfs 또는 bfs로 풀 수 있는 문제인데, dfs로 풀어보도록 하겠습니다. 

각 노드를 생성하고, 간선을 연결하여 graph를 만들어 줍니다. 

그리고 각 노드에 대하여 dfs를 진행하도록 하는데, 각 노드에 방문하였다면 skip합니다.

이때 노드에 방문하지 않고, dfs를 진행하도록 하면 count를 올려줍니다. 

dfs를 진행하면서 각 노드에 대하여 visited[node]에 방문했는지 여부를 설정합니다.  

이 동작을 반복하다보면 count를 구할 수 있게 됩니다. 

전체 코드

import sys
sys.setrecursionlimit(10000)

def dfs(index, V, G):
	V[index] = 1
	for i in range(1, N+1):
		if index == i or V[i] == 1 or G[index][i] == 0:
			continue
		dfs(i, V, G)

MAX = 1001
# 입력
N, M = map(int, input().split(' '))

# 변수 설정
graph = [[0] * (MAX+1) for i in range(MAX+1)]
visited = [0] * (MAX+1)
cnt = 0

for i in range(M):
	u, v = map(int, sys.stdin.readline().split())

	## graph u->v, v->u 설정
	graph[u][v] = 1
	graph[v][u] = 1

for i in range(1, N+1):
	if visited[i] == 0:
		dfs(i, visited, graph)
		cnt += 1


print(cnt)

파이썬 / 백준 알고리즘 / 1260번 DFS와 BFS 문제 및 풀이

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

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.
한 간선이 여러 번 주어질 수도 있는데, 간선이 하나만 있는 것으로 생각하면 된다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 및 출력

문제 풀이

너비우선탐색(BFS, Breadth First Search)와 깊이우선탐색(Depth First Search)의 전형적인 기초 문제입니다. 이 두 알고리즘은 그래프를 탐색하기 위한 알고리즘으로 모든 정점을 탐색하기 위해 사용됩니다.

DFS는 한 경로로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 경로로 탐색하는 방식이고,(스택의 방식을 이용함, 스택은 기본 동작이라 스택 자료 구조를 이용할 필요는 없음)
BFS는 갈림길에 연결되어 있는 모든 경로를 한번씩 탐색한 뒤 다시 연결되어 있는 모든 경로를 넓게 탐색하는 방식입니다. (자료 구조 큐 또는 덱 구조를 이용해야 함)

예를 들어 아래와 같은 그래프에서 DFS 동작은 다음과 같습니다. 
1) 정점 1에서부터 검색 시작
2) 1에 연결된 정점 2,3,4 중 가장 작은 수인 2(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨)를 방문
3) 2에 연결된 정점 4를 방문
4) 4에 연결된 정점 3을 방문
5) 더이상 방문할 정점이 없으므로 종료
- 결국 1->2->4->3 순으로 방문하게 됩니다

예를 들어 아래와 같은 그래프에서 BFS 동작은 다음과 같습니다.
1) 정점 1에서부터 검색 시작 
2) 정점 1과 연결된 2를 검색(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨) 
3) 정점 1과 연결된 3을 검색(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨) 
4) 정점 1과 연결된 4를 검색 
- 결국 1->2->3->4 순으로 방문하게 됩니다. 

전체 코드

from collections import deque

def dfs(v):
    print(v, end=' ')
    visit[v] = 1
    for i in range(1, n + 1):
        if visit[i] == 0 and adj[v][i] == 1:
            dfs(i)

def bfs(v):
    queue = deque()
    visit[v] = 1
    queue.append(v)

    while (queue):
        v = queue.popleft()
        print(v, end=' ')
        for i in range(1, n + 1):
            if visit[i] == 0 and adj[v][i] == 1:
                queue.append(i)
                visit[i] = 1

#입력 n : 정점의 개수, m : 간선의 개수, v : 탐색을 시작할 정점의 번호
n, m, v = map(int, input().split())
adj = [[0] * (n + 1) for i in range(n + 1)]
visit = [0 for i in range(n + 1)]
for i in range(m):
    x, y = map(int, input().split())
    adj[x][y] = 1
    adj[y][x] = 1

#출력
dfs(v)
print()

visit = [0 for i in range(n + 1)]
bfs(v)