해커를 꿈꾸는 개발자

파이썬 / 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 백준 / 15650번 N과 M(2) - 백트래킹

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

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 고른 수열은 오름차순이어야 한다.

풀이

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

https://zidarn87.tistory.com/329

2. 재귀함수를 이용하고, 출력하려는 리스트의 개수가 m개 이면 리스트의 내용을 출력하도록 합니다.

3. 재귀함수에서는 전달받은 인자인 start부터 n까지 숫자를 사용합니다. 재귀함수를 호출할 때에는 i+1을 호출하여 줍니다. 그러면 오름차순으로 리스트에 들어가게 됩니다. 

전체 코드

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

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

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

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

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

문제

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

풀이

1. 백트래킹을 이용하여 풀 수 있는 문제입니다. 백트래킹의 가장 기초적인 문제라 할 수 있습니다.

2. 재귀함수를 이용하고, 그 재귀함수에는 숫자의 개수를 전달하여, 그 개수가 m개 이면 리스트의 내용을 출력하도록 합니다.

3. 재귀함수에서 개수가 m개가 아니라면, n까지의 숫자들을 확인하고, 방문하였는지 체크하여, 방문하지 않은 숫자를 기준으로 가지치기(재귀함수 호출)를 합니다.

N = 4, M = 3인 경우, 위와 같이 깊이우선탐색의 순서대로 방문하여, 리스트를 출력하는 방식으로 합니다. 

위 그림에서 2, 3, 4가 루트인 경우에도 동일한 방식으로하여 구하면 됩니다. 

전체 코드

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

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

    for i in range(N):
        if not visited[i]:
            visited[i] = True
            lst.append(i+1)
            dfs(depth+1)
            visited[i] = False
            lst.pop()

파이썬 / 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)