BFS/DFS
BFS와 DFS은 완전탐색처럼 graph 전체를 탐색하는 방식이지만 조금더 효율적으로 탐색하는 방식이다. Breadth First Search (BFS)은 너비우선탐색을 의미하며 graph node에서 인접한 노드를 차례대로 방문하는 방식이다. Depth First Search (DFS)은 깊이우선탐색을 의미하며 graph node에서 최대한 깊숙히 내려갈 수 있을 때까지 (막다른 길이 나올 때까지) 방문하는 방식이다.
문제
타겟 넘버
https://programmers.co.kr/learn/courses/30/lessons/43165
문제
n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.
예시
## numbers target return
[1, 1, 1, 1, 1] 3 5
풀이
주어지는 numbers의 개수에 들어갈 부호의 경우의 수를 구하면 되므로 2의 n제곱 복잡도를 갖는다. 경우의 수 중 하나가 완성될 때까지 탐색을 해야하므로 DFS 방식으로 풀면 된다. +와 -의 모든 경우의 수를 구해보자. 간단하게 트리를 그려보면 다음과 같다.
[+ -]
.
. .
[+ -] [+ -]
. .
. . . .
[+ -] [+ -] [+ -] [+ -]
조잡하지만 위와 같은 방식으로 len(numbers) 만큼의 depth까지 내려갈 것이다. 그리고 매 순간 (level)의 선택은 + 또는 - 이므로 visited은 [0, 0] 이면 된다. 경우의 수 (다른 경로도 탐색) 이므로 백트래킹을 이용한다.
def solution(numbers, target):
answer = 0
# 숫자의 순서는 상관없음
# 숫자 앞의 부호가 +, -인 경우의 수를 구하면되므로 2^20의 복잡도
sign = ['+', '-']
visited = [0, 0]
chosen = []
result = []
def recur():
for i in range(len(sign)):
visited[i] = 1
chosen.append(sign[i])
recur()
visited[i] = 0
chosen.pop()
recur()
answer = len(result)
return answer
그리고 재귀의 return 조건은 선택된 부호가 포함된 숫자를 더했을 때 target 과 같으면 되므로 return 조건을 추가한다.
def solution(numbers, target):
answer = 0
# 숫자의 순서는 상관없음
# 숫자 앞의 부호가 +, -인 경우의 수를 구하면되므로 2^20의 복잡도
sign = ['+', '-']
visited = [0, 0]
chosen = []
result = []
def recur():
if len(chosen) == len(numbers):
sum = 0
# chosen loop 돌아가면서 연산
for i, s in enumerate(chosen):
if s == '+':
sum += numbers[i]
else:
sum -= numbers[i]
if sum == target:
result.append(sum)
return
for i in range(len(sign)):
visited[i] = 1
chosen.append(sign[i])
recur()
visited[i] = 0
chosen.pop()
recur()
answer = len(result)
return answer
네트워크
https://programmers.co.kr/learn/courses/30/lessons/43162
문제
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
제한사항
컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
computer[i][i]는 항상 1입니다.
예시
## n, computers, return
3 [[1, 1, 0], [1, 1, 0], [0, 0, 1]] 2
3 [[1, 1, 0], [1, 1, 1], [0, 1, 1]] 1
풀이
이 문제는 어떤 결과를 원하는지 조금 이해하기 어려울 수도 있다. 네트워크란 하나의 edge을 포함하기만 하더라도 그와 연결된 모든 node은 하나의 네트워크를 의미한다. 예를들어 A, B, C, D, E라는 컴퓨터가 있을 때, 다음과 같이 edge가 연결되어 있다고 하자.
A ㅡ B
ㄴ C
ㄴ D ㅡ E
위와 같을 경우에 A, B, C, D, E가 하나의 네트워크에 있다는 뜻이다. 이 그림을 90도 돌려보면 tree 형태임을 알 수 있다! 그리고 좌우로 확인해가면서 edge로 연결되어 있는지 확인하면 같은 네트워크인지 알 수 있다. 즉, BFS을 이용하면 된다.
def solution(n, computers):
# 1ㅡ2
# ㄴ3 으로 연결되어 있으면 2, 3이 연결되어 있지 않더라도 하나의 네트워크이므로 BFS를 사용하자
q = []
visited = [0 for _ in range(n)]
def bfs():
answer = 0
# 모든 node를 검사할 때까지 loop을 돌린다 (visited에 0이 없을 때 까지)
while 0 in visited:
# visited가 0인 최초값 넣기
q.append(visited.index(0))
visited[visited.index(0)] = 1
while q:
j = q.pop(0)
for i in range(n):
# 방문하지 않았을 때 and 앞뒤 node가 연결되어 있을 때
if visited[i] == 0 and computers[j][i] == 1:
q.append(i)
visited[i] = 1
answer += 1
return answer
answer = bfs()
return answer
단어변환
https://programmers.co.kr/learn/courses/30/lessons/43163
문제
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.
제한사항
각 단어는 알파벳 소문자로만 이루어져 있습니다.
각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
begin과 target은 같지 않습니다.
변환할 수 없는 경우에는 0를 return 합니다.
예시
## begin target words return
hit cog [hot, dot, dog, lot, log, cog] 4
hit cog [hot, dot, dog, lot, log] 0
풀이
기준점에서 알파벳을 바꿔가며 words 안에 있는 단어와 일치하는지 확인하면 된다. 최소 단계를 구하는 것이므로 BFS로 해결해야할 확률이 높다. hit 단어로 시작할 때, 첫번째 자리인 h 을 a ~ z 문자로 바꾸고 words에 있는 단어라면 q에 집어넣는다. 이 방식을 계속 이어나가면 1번 바꾸었을 때, 2번 바꾸었을 때, … 단계별로 tree 구조를 형성하며 내려가는 것을 상상해볼 수 있다. 조심해야하는 점은 그 전에 만났던 단어는 제외해야한다.
def solution(begin, target, words):
# 26*10*50
# BFS (최소거리 구하기)
alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
# 만들었던 단어는 다시 만들면 안됨 (dictionary에 저장)
answer = 0
q = []
visited = []
cnt_list = []
visited.append(begin)
q.append(begin)
cnt_list.append(0)
while q:
now = q.pop(0)
cnt = cnt_list.pop(0)
if now == target:
print(now)
answer = cnt
return answer
for n in range(len(now)):
new = now
new_list = list(new)
for a in alpha:
new_list[n] = a
new_word = ''.join(new_list)
# 처음보는 단어 and words 안에 있는 단어
if not new_word in visited and new_word in words:
q.append(new_word)
visited.append(new_word)
cnt_list.append(cnt+1)
return answer
여행경로
https://programmers.co.kr/learn/courses/30/lessons/43164
문제
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
모든 공항은 알파벳 대문자 3글자로 이루어집니다.
주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
예시
## tickets, return
[[ICN, JFK], [HND, IAD], [JFK, HND]] [ICN, JFK, HND, IAD]
[[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO]
예제 #1
[ICN, JFK, HND, IAD] 순으로 방문할 수 있습니다.
예제 #2
[ICN, SFO, ATL, ICN, ATL, SFO] 순으로 방문할 수도 있지만 [ICN, ATL, ICN, SFO, ATL, SFO] 가 알파벳 순으로 앞섭니다.
풀이
조건에 맞는 경로를 탐색하는 문제이므로 DFS로 풀어야할 확률이 높다. ICN 에서 시작하므로 ICN 으로 시작하는 티켓을 찾아야 하고, 그 티켓들의 각각 도착지점을 출발지로 하는 티켓을 또 찾아서 나열해 나아가야 한다. 이런식으로 graph을 그리면 tree 구조로 형성하면서 내려가는 것을 알 수 있다. visited 배열과 백트래킹을 적절히 이용하여 모든 경로를 찾고 이 경로 중에서 알파벳 순서 우위에 있는 것을 return하면 된다. 알파벳 순서는 간단히 sorted 을 사용하면 된다.
def solution(tickets):
# DFS
# 모든 곳 방문하면 return
# 마지막에 오름차순으로 확인
answer = []
s = []
visited = [0 for _ in tickets]
answer_list = []
# ICN 넣기
s.append(["ICN", "ICN"])
def dfs():
# visited가 모두 1이 될 때까지
if not 0 in visited:
nation_list = [s[i][1] for i in range(0, len(s))]
answer_list.append(nation_list)
return
for i, ticket in enumerate(tickets):
now = s[-1]
if now[1] == ticket[0] and visited[i] == 0:
s.append(ticket)
visited[i] = 1
dfs()
s.pop()
visited[i] = 0
dfs()
answer = sorted(answer_list)[0]
return answer