✅ DFS/BFS
🎈 타겟 넘버
numbers로 숫자들을 입력받고, 해당 숫자들의 +- 조합으로 target값을 만들 수 있는 범위의 개수를 구하는 문제.
# DFS
answer = 0
def dfs(idx, num, numbers, target):
global answer
if idx == len(numbers):
if num == target:
answer += 1
return
else:
dfs(idx+1, num+numbers[idx], numbers, target)
dfs(idx+1, num-numbers[idx], numbers, target)
def solution(numbers, target):
global answer
dfs(0, 0, numbers, target)
return answer
# BFS
from collections import deque
def solution(numbers, target):
answer = 0
queue = deque()
queue.append([0, numbers[0]])
queue.append([0, -1*numbers[0]])
while queue:
idx, num = queue.popleft()
idx += 1
if idx == len(numbers):
if num == target:
answer += 1
else:
queue.append([idx, num+numbers[idx]])
queue.append([idx, num-numbers[idx]])
return answer< 풀이 과정 >
DFS와 BFS로 풀이를 진행했다. 각각 살펴보면 다음과 같다.
- DFS : idx로 주어진 numbers의 인덱스로 숫자를 살펴보고, num으로 numbers의 숫자 조합 결과가 target과 일치하면 answer + 1처리를 한다. 아닌 경우 재귀함수로 다음 인덱스를 탐색한다.
- BFS : deque를 만들고, idx와 num을 반복하여 꺼내며 주어진 numbers내 숫자들의 조합으로 target값과 동일하면 answer + 1처리를 하고, idx를 1개씩 늘리며 queue에 +- numbers[다음 인덱스]로 반복 탐색을 진행한다.
🎈 네트워크
컴퓨터 개수 n, 연결에 대한 정보 computers가 주어질 때 연결된 네트워크 개수를 리턴하는 문제. computers는 n개의 노드로 주어지고, 연결된 노드끼리 1로 표시되고 연결이 안되있는 부분은 0으로 표시된다.
# DFS
def solution(n, computers):
answer = 0
visited = [0] * n
def dfs(node):
visited[node] = 1
for i in range(n):
if not visited[i] and computers[node][i]:
dfs(i)
for i in range(n):
if not visited[i]:
dfs(i)
answer += 1
return answer
# BFS
from collections import deque
def solution(n, computers):
answer = 0
visited = [0]*n
def bfs(v):
queue = deque()
queue.append(v)
while queue:
x = queue.popleft()
visited[x] = 1
for i in range(n):
if not visited[i] and computers[x][i]:
queue.append(i)
for i in range(n):
if not visited[i]:
bfs(i)
answer += 1
return answer< 풀이 과정 >
- DFS : 노드 방문 여부를 나타낸 visited를 만들고, 현재 위치는 방문처리 후 다음 위치가 방문한적 없고, 값이 1인 경우만 재귀함수로 반복해준다.
- BFS : DFS와 마찬가지로 방문 여부를 나타낸 visited를 만들고, queue에 값을 꺼내며 방문 처리를 진행한다. 이후 computers 내 값이 1이고, 방문하지 않은 노드에 한해 큐에 추가하며 탐색한다.
🎈 게임 맵 최단거리
nxm 크기의 게임 맵이 2차원 배열로 주어지고, 처음 캐릭터가 1,1에 위치해있다. 상대팀 진영은 n,m에 위치해있고 (1,1)에서 (n,m)으로 가는 최단 이동 횟수를 구하는 문제
from collections import deque
def solution(maps):
answer = 0
# 가로 세로 각각 n, m으로 표시
n = len(maps)
m = len(maps[0])
# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# nxm 크기의 방문여부 생성 후 현재 캐릭터 위치 방문처리
visited = [[0]*m for _ in range(n)]
visited[0][0] = 1
# deque만들고 현위치 큐에 삽입
queue = deque()
queue.append((0, 0))
# 큐 빌때까지 반복
while queue:
x, y = queue.popleft()
# 상대방 진영 도착 시 값 리턴
if x == n-1 and y == m-1:
return visited[x][y]
# 상하좌우 4방향 탐색 시작
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 다음 위치가 주어진 maps 범위 내, 방문안한곳, 다음 값이 1이면 탐색 실행
if 0<=nx<n and 0<=ny<m and not visited[nx][ny] and maps[nx][ny] == 1:
queue.append((nx, ny))
visited[nx][ny] = visited[x][y] + 1
return -1< 풀이 과정 >
n, m을 주어진 maps를 통해 만들어주고, 방문한 곳 재방문하지 않기 위해 visited생성하고 현위치 방문처리한 후, 이동을 위해 dx, dy를 만들고 현위치를 deque에 삽입하였다.
이후 queue가 빌때까지 반복하는데 다음 위치가 상대방 진영인 (n,m)이면 리턴하고, 아닌 경우 주어진 조건 내 범위를 만족하며 다음 위치를 큐에 삽입하고 visited+1해주며 탐색한다.
🎈 단어 변환
begin 단어가 주어지고 target으로 바꾸는 데, 주어진 words의 단어로 변환해야 한다.
이때 변환 시 한 번에 한 단어만 변경할 수 있다. 최종적으로 단어를 변환한 횟수를 리턴하는 문제
from collections import deque
def solution(begin, target, words):
answer = 0
if target not in words:
return 0
queue = deque()
queue.append([begin, 0])
while queue:
x, cnt = queue.popleft()
if x == target:
return cnt
for i in range(len(words)):
word = words[i]
diff = 0
for j in range(len(x)):
if x[j] != word[j]:
diff += 1
if diff == 1:
queue.append([word, cnt+1])< 풀이 과정 >
BFS로 구현해 풀이하였다.
- 우선, 주어진 words내 target이 없다면 0을 리턴하도록 하고 queue에 begin과 횟수를 집어넣는다.
- 이후 queue에서 단어 x와 횟수 cnt를 꺼내고 x가 target이라면 횟수 cnt를 그대로 리턴한다.
- 아닌 경우, words 내 단어 word를 지정하고 한 개의 알파벳만 차이를 보여주기 위해 diff변수를 지정한다.
- 2중 for문으로 다음 단어가 word단어와 비교하여 알파벳이 1개만 차이난다면 queue에 다음값, 횟수+1을 삽입하여 이어서 탐색한다
🎈 여행경로
출발지, 도착지로 구성된 tickets 배열이 주어지고 해당 경로를 모두 지나는 배열을 리턴하는 문제
from collections import deque
def solution(tickets):
answer = []
# 주어진 tickets에 도착지를 오름차순 정렬
tickets.sort(key = lambda x: x[1])
# 큐에 현재 공항, 경로, ticket 사용 여부를 큐에 삽입
queue = deque()
queue.append(('ICN', ['ICN'], []))
while queue:
큐에서 매번 빼내면서
airport, route, visited = queue.popleft()
# 티켓 모두 사용한 경우, answer에 추가
if len(visited) == len(tickets):
answer.append(route)
# tickets를 enumerate로 탐색해, 티켓 인덱스, (출발, 도착) for문으로 순회
for idx, ticket in enumerate(tickets):
# 출발지가 현재 공항위치고 아직 사용하지 않은 티켓인 경우
if ticket[0] == airport and not idx in visited:
# 큐에 도착지, 경로 + 도착지, 티켓 사용한 인덱스를 다시 삽입한다.
queue.append((ticket[1], route + [ticket[1]], visited + [idx]))
# 모든 경로에 대해 주어졌으므로, 제일 첫번째 리스트만 출력
return answer[0]< 풀이 과정 >
bfs 탐색으로 구현한 풀이
- 최종적으로 정렬된 경로를 출력하기 위해 도착지를 우선 정렬해준다
- 큐에 현재공항, 경로, 티켓사용여부를 삽입하여 while문으로 반복 탐색한다.
- 티켓 사용 수와 전체 티켓 수가 일치하면 answer에 경로만 추가해준다.
- for문으로 tickets를 돌며 출발지가 현재 공항이고, 아직 사용안한 티켓인 경우, 다음 위치 큐에 삽입해주고 answer리스트의 첫 번째 리스트만 출력한다.
🎈 아이템 줍기 (BFS)
rectangle로 x1,y1, x2,y2가 주어진다. 이때 x1,y1은 직사각형의 왼쪽 아래 꼭지점이고 x2, y2는 오른쪽 위 꼭지점을 의미한다. 경로는 테두리를 따라서만 이동이 가능하고 시작점은 characterX, characterY 이고 도착점은 itemX, itemY일때 최소 경로를 찾는 문제
다음과 같은 직사각형 조건이 추가된다.
- 직사각형 간의 서로 꼭지점에서 만나거나 변이 겹치는 경우는 없다.
- 지형이 2개로 분리되는 경우는 없다. (직사각형이 한 덩어리로 뭉쳐있다는 말)
- 한 직사각형이 다른 직사각형 내 완전히 포함되는 경우도 없다.
from collections import deque
def solution(rectangle, characterX, characterY, itemX, itemY):
answer = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
n = 102
graph = [[5]*n for _ in range(n)]
for loc in rectangle:
x1, y1, x2, y2 = map(lambda x: x*2, loc)
for i in range(x1, x2+1):
for j in range(y1, y2+1):
if x1<i<x2 and y1<j<y2:
graph[i][j] = 0
elif graph[i][j] != 0:
graph[i][j] = 1
queue = deque()
queue.append((characterX*2, characterY*2))
visited = [[0]*n for _ in range(n)]
visited[characterX*2][characterY*2] = 1
while queue:
x, y = queue.popleft()
if x == itemX*2 and y == itemY*2:
answer = (visited[x][y] - 1)//2
break
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if not visited[nx][ny] and graph[nx][ny] == 1:
queue.append((nx, ny))
visited[nx][ny] = visited[x][y] + 1
return answer< 풀이 과정 >
그래프 크기를 2배 곱해주어야만 해결할 수 있는 문제. 그 이유는 다음과 같다.
주어진 입출력 예시에서 (3,5)에서 테두리를 따라 (4,5)로 이동하고 (5,5)로 이동해야 하는데, 2배를 안해주게 되면 (3,6)좌표도 경로에 포함되므로 (3,5)에서 (3,6)으로 바로 경로를 탐색하는 문제가 발생하게 된다.
따라서 0.5 단위로 끊는다는 개념으로 이해하고 전체 SIZE를 2배 키워 리턴 시에도 값을 2로 나눈 값을 리턴해주면 된다.문제 풀이한 코드 해석을 하면 다음과 같다.
(방문 여부를 따지기 위한 visited, dx, dy 등을 부여해주고 graph 생성을 위해 512를 해준 102X102 크기의 그래프를 만들어 준다. 그 이후 rectangle을 통해 입력받은 x,y 좌표도 2배를 해주고 주어진 x1~x2, y1~y2 내에 속한 내부 범위를 0으로 처리하고 테두리는 1로 처리한다.
이후 queue에 초기값 characterX, characterY를 각각 2배해준 값을 삽입하고 방문처리한 후 itemX2, itemY*2해준 값과 일치하면 answer에 리턴하고 상하좌우로 다음 위치로의 탐색을 진행해 방문하지 않은 곳이고, 테두리이면 이동하는 방식으로 구현하였다.
🎈 퍼즐 조각 채우기 - (아직 해결 X)
game_board로 빈칸이 0, 채워진 칸이 1로 나타낸 그래프와, 도형이 주어진 table 입력값이 있을 때 table에 존재하는 도형으로 game_board에 채울 수 있는 최대 칸을 출력하는 문제
이때, 도형은 회전시킬 수도 있지만 뒤집을 수는 없고, game_board에 새로 채워 넣은 퍼즐 조각과 인접한 빈칸이 존재해선 안된다.
결과적으로, table의 존재하는 조각을 찾아 game_board 빈 공간에 조각을 회전시켜가면서 채울 수 있는지 확인하는 것
✅ 문제 풀이
🎈 무인도 여행
maps 입력값으로 무인도 지도가 nxm 크기로 주어지고 격자 칸 내에는 1~9까지 숫자가 적혀있는데, 덩어리로 이루어진 무인도에서 최대 며칠동안 머물 수 있는지 확인하는 문제
from collections import deque
def bfs(maps, n, m, visited, i, j):
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()
queue.append((i, j))
visited[i][j] = 1
day = 0
while queue:
x, y = queue.popleft()
day += int(maps[x][y])
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<m and not visited[nx][ny] and maps[nx][ny] != 'X':
queue.append((nx, ny))
visited[nx][ny] = 1
return day
def solution(maps):
answer = []
n = len(maps)
m = len(maps[0])
visited = [[0]*m for _ in range(n)]
for i in range(n):
for j in range(m):
if not visited[i][j] and maps[i][j] != 'X':
answer.append(bfs(maps, n, m, visited, i, j))
if answer:
return sorted(answer)
else:
return [-1]< 풀이 과정 >
bfs함수를 따로 만들어서 구현하였다.
- bfs함수를 통해 상하좌우 4방향으로 탐색을 진행하여 현재 위치부터 시작해 다음위치에 존재하는 maps[x][y]값을 더해주면서 탐색한다. 이때 주어진 maps는 문자형이므로 int형으로 변환하여 day에 더해준다. 탐색 시작전에, 방문하지 않은 곳과 X표시가 아닌 곳으로 조건을 걸어주어야 한다.
- solution함수로 주어진 maps의 세로, 가로 길이를 미리 지정하고 answer에 bfs함수의 리턴 결과인 day를 추가해주며 탐색을 진행한다.
🎈 마법의 엘리베이터
엘리베이터는 -1, +1, -10, +10, -100, +100 등 절댓값이 10^c 형태인 정수들이 적힌 버튼으로 구성되어 있다. 버튼을 누르면 현재 층 수에 버튼에 적힌 값을 더한 층으로 이동하게 되고, 단 이동한 층이 0보다 작다면 엘리베이터는 움직이지 않는다고 한다. 현재 엘리베이터 층 수가 주어지고, 0층에 도착하는 최소 이동 횟수를 찾는 문제
def solution(storey):
answer = 0
while storey:
n = storey % 10
if n > 5 or n == 5 and storey//10 % 10 >= 5:
answer += 10-n
storey += 10-n
else:
answer += n
storey //= 10
return answer< 풀이 과정 >
storey가 0이 될 때까지 while문을 사용하여 반복한다.
storey를 10으로 나눈 나머지를 n으로 두고, n이 5보다 크다면 0쪽으로 -1하는 것보다 +1해서 10을 만드는 것이 더 빠르고, 현재 자리 수가 5이고 다음 자리 수가 5보다 크다면 마찬가지로 100을 만드는 것이 더 빠른 것을 알 수 있다.
따라서, answer, storey 모두 10-n만큼 더해주고, 아닌 경우 answer에 n만 더해준다
if문을 거치며 storey는 10으로 나눈 몫만 남겨두는 처리 형태로 반복하여 구현한다.
