프로그래머스 - 알고리즘 고득점 Kit 깊이/너비 우선 탐색(DFS/BFS) 풀이 모음
: 프로그래머스 코딩테스트 연습 Python 알고리즘별로 풀어보기
🔍 깊이/너비 우선 탐색(DFS/BFS) > 타겟 넘버
클릭해서 문제 전체 보기🔼
📖 풀이 코드
from collections import deque
def solution(numbers, target):
queue = deque()
result = 0
def bfs():
queue.append([numbers[0], 0])
queue.append([-numbers[0], 0])
while len(queue) > 0:
num, idx = queue.popleft()
idx += 1
if idx < len(numbers):
queue.append([numbers[idx] + num, idx])
queue.append([-numbers[idx] + num, idx])
elif num == target:
nonlocal result
result += 1
bfs()
return result📢 풀이 설명
popleft로 빼낸 값을 다음 idx에 해당하는 값에 더해야하니까, queue에 값과 idx를 같이 저장했다.
그 후, idx가 마지막에 이르르면 target과 비교한 후 값이 같으면 result를 1 증가시킨다.
- 여기서 나온 nonlocal이란, 지역변수가 아닌 값을 사용하겠다는 선언이다.
🔍 깊이/너비 우선 탐색(DFS/BFS) > 네트워크
클릭해서 문제 전체 보기🔼
📖 풀이 코드
def solution(n, computers):
n = len(computers)
count = 0
graph = []
for (idx1, connection) in enumerate(computers):
tmpList = []
for (idx2, i) in enumerate(connection):
if idx1 == idx2: continue
elif i == 1: tmpList.append(idx2)
graph.append(tmpList)
visited = [False for _ in range(n)]
def dfs(idx):
visited[idx] = True
for i in graph[idx]:
if not visited[i]: dfs(i)
for idx in range(n):
if not visited[idx]:
count += 1
dfs(idx)
return count📢 풀이 설명
전형적인 dfs 문제이다. 각 노드별로 연결된 노드들을 모아 graph로 만들고, 0부터 n까지 루프를 돌며 방문한 적 없는 노드에 dfs를 돌리며 count를 센다.
🔍 깊이/너비 우선 탐색(DFS/BFS) > 게임 맵 최단거리
클릭해서 문제 전체 보기🔼
📖 풀이 코드
from collections import deque
def solution(maps):
n = len(maps)
m = len(maps[0])
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
def bfs(i, j, c):
queue = deque([(i, j, c)])
while queue:
y, x, count = queue.popleft()
for d in range(4):
ny = y + dy[d]
nx = x + dx[d]
if ny == n - 1 and nx == m - 1: return count + 1
if ny < 0 or nx < 0 or ny >= n or nx >= m or maps[ny][nx] == 0: continue
maps[ny][nx] = 0
queue.append((ny, nx, count + 1))
return -1
return bfs(0, 0, 1)📢 풀이 설명
기본 bfs 문제이다. 상하좌우로 움직이며, 이동하려는 칸이 1일 경우 이동 후 0으로 바꾼다. 이렇게 최단거리를 찾는다.
🔍 깊이/너비 우선 탐색(DFS/BFS) > 단어 변환
클릭해서 문제 전체 보기🔼
📖 풀이 코드
from collections import deque
def solution(begin, target, words):
strLen = len(begin)
if target not in words: return 0
def checkWords(word1, word2):
count = 0
for i in range(strLen):
if word1[i] != word2[i]: count += 1
return True if count == 1 else False
usedWords = set()
def bfs(begin, count):
queue = deque()
queue.append((begin, count))
while queue:
curStr, count = queue.popleft()
if curStr == target: return count
for word in words:
if word not in usedWords and checkWords(curStr, word):
usedWords.add(word)
queue.append((word, count + 1))
return 0
return bfs(begin, 0)📢 풀이 설명
두 단어가 한 글자만 다른 걸 어떻게 알아내지..? 고민하다가 checkWords 함수를 하나 만들었다. 이 함수 없이 일일이 비교하니까 시간 초과 발생했었음... 풀이의 흐름은 아래와 같다.
- target이 words 안에 있는지 확인 -> 없으면 바로 0 리턴
- checkWords 함수 생성 -> 두 단어가 1글자만 다른지 확인
- bfs 함수 생성 -> begin에서 target이 될 때까지의 count 세기
- 결과값인 count 리턴
🔍 깊이/너비 우선 탐색(DFS/BFS) > 아이템 줍기
클릭해서 문제 전체 보기🔼
📖 풀이 코드
from collections import deque
def solution(rectangle, characterX, characterY, itemX, itemY):
graph = [[0] * 101 for _ in range(101)]
for x1, y1, x2, y2 in rectangle:
x1, y1, x2, y2 = x1 * 2, y1 * 2, x2 * 2, y2 * 2
for y in range(y1, y2 + 1):
for x in range(x1, x2 + 1):
if x > x1 and x < x2 and y > y1 and y < y2: graph[y][x] = 1
elif graph[y][x] != 1: graph[y][x] = 2
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
def bfs(characterY, characterX):
queue = deque([(characterY, characterX, 1)])
while queue:
curY, curX, count = queue.popleft()
for d in range(4):
nY = curY + dy[d]
nX = curX + dx[d]
if nY == itemY and nX == itemX: return count // 2
if nY < 0 or nY > 100 or nX < 0 or nX > 100: continue
if graph[nY][nX] == 2:
graph[nY][nX] = -1
queue.append((nY, nX, count + 1))
itemX, itemY = itemX * 2, itemY * 2
return bfs(characterY * 2, characterX * 2)📢 풀이 설명
이런 문제 유형을 접해보지 못해서 못 풀 것 같아 다른 사람들의 풀이를 참고했다. 이 문제의 핵심은 각 값을 2배로 키워서 계산하는 것이다.
이 문제는 겹쳐진 사각형들이 만든 최종 테두리만 따라가야 한다. 이때 값을 그대로 사용하면 테두리가 불분명해져 오류가 생기기 쉽다.
왜 2배씩 곱해서 풀어야하는지 이해가 되지 않을 때는 그림으로 그려보면 이해하기 쉽다.
그래프의 한 칸은 점이 아닌 면이기 때문에, 왼쪽처럼 선으로 그렸다고 생각할 수 있지만 실제로는 오른쪽처럼 색칠이 되어있다.
이렇게 되면 bfs 탐색 중 예상치 못한 방향으로 먼저 가버려서 길을 잃어 오류를 발생시킬 수 있다. 따라서 2배씩 확대한 뒤 그리면 이러한 상황을 방지할 수 있다 !
그 후에는 일반적인 bfs처럼 풀고, 답만 2배로 나눠주면 된다.
🔍 깊이/너비 우선 탐색(DFS/BFS) > 여행 경로
클릭해서 문제 전체 보기🔼
📖 풀이 코드
def solution(tickets):
result = []
airportDict = dict()
for (a, b) in tickets:
if a in airportDict: airportDict.get(a).append(b)
else: airportDict[a] = [b]
for (key, value) in airportDict.items():
value.sort(reverse = True)
stack = ["ICN"]
while stack:
if stack[-1] not in airportDict or len(airportDict.get(stack[-1])) == 0:
result.append(stack.pop())
else: stack.append(airportDict.get(stack[-1]).pop())
result.reverse()
return result📢 풀이 설명
나는 그래프 문제라기보다는 스택문제라고 느꼈다. 나의 풀이 방법은 아래와 같다.
주어진 ticket들을 dict에 List로 정리하고, 그 List를 거꾸로 정렬한다.
그 후 시작점인 "ICN"부터 stack에 넣고 stack 마지막 값을 key로 가진 dict을 조회하며
1. 존재하지 않거나, 해당 key의 value가 비어있는 경우 stack에서 빼서 result에 넣는다
2. 존재한다면 해당 key의 value중 마지막 값을 빼서 stack에 넣는다.
이 과정을 반복하다보면 result에 도착하는 순서가 맨 위에 오도록 완성된다.
출발하는 순서대로 값을 담아야하므로 reverse한 뒤 return하면 된다.
주어진 테스트케이스는 맞는데 제출하면 틀렸었다. 그래서 다른 테케를 찾아보다가 답이 틀리는 케이스를 발견해서 수정했더니 통과했다.
제출에서 틀리는 분들은 아래 테스트케이스 한번 추가해서 돌려보세요 ㅎㅎ
입력: [["ICN", "AAA"], ["ICN", "BBB"], ["ICN", "CCC"], ["CCC", "ICN"], ["BBB", "ICN"]]
출력: ["ICN", "BBB", "ICN", "CCC", "ICN", "AAA"]
🔍 깊이/너비 우선 탐색(DFS/BFS) > 퍼즐 조각 채우기
클릭해서 문제 전체 보기🔼
📖 풀이 코드
from collections import deque
def solution(game_board, table):
n = len(game_board)
result = 0
def findBlocks(board, num):
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
def bfs(i, j):
queue = deque([(i, j)])
visited[i][j] = True
block = [(0, 0)]
while queue:
y, x = queue.popleft()
for d in range(4):
ny = y + dy[d]
nx = x + dx[d]
if ny < 0 or ny >= n or nx < 0 or nx >= n: continue
if not visited[ny][nx] and board[ny][nx] == num:
visited[ny][nx] = True
queue.append((ny, nx))
block.append((ny - i, nx - j))
return block
visited = [[False] * n for _ in range(n)]
blocks = []
for i in range(n):
for j in range(n):
if not visited[i][j] and board[i][j] == num: blocks.append(bfs(i, j))
return blocks
def rotateBlock(block):
return [(-x, y) for y, x in block]
def sortBlock(block):
block.sort()
minY, minX = block[0]
return sorted((y - minY, x - minX) for y, x in block)
gameBoardBlocks = findBlocks(game_board, 0)
sortGameBoardBlocks = [sortBlock(block) for block in gameBoardBlocks]
tableBlocks = findBlocks(table, 1)
sortTableBlocks = [sortBlock(block) for block in tableBlocks]
usedList = [False] * len(sortTableBlocks)
for gameBoard in sortGameBoardBlocks:
for (idx, table) in enumerate(sortTableBlocks):
if usedList[idx]: continue
flag = False
for _ in range(4):
if gameBoard == table:
flag = True
break
table = sortBlock(rotateBlock(table))
if flag:
usedList[idx] = True
result += len(table)
break
return result📢 풀이 설명
어렵고 복잡한 문제였다.. 풀고 보면 로직이 복잡하진 않지만 함수 여러 개를 생각해내기 어려웠음 😭 풀이법은 다음과 같다.
- game_board, table에 놓인 각각 빈공간 & 블럭들 찾는 함수
findBlocks생성
-> 그래프를 통째로 넘겨 이 함수 안에서 for문을 돌며 빈공간 & 블럭들을 찾음
-> 상하좌우로 연결된 하나의 블럭을 찾아야하니까 안에bfs함수도 만들어서 사용
- 블럭을 시계방향으로 회전시키는
rotateBlock함수를 생성
- 블럭을 상대좌표로 정렬시키는
sortBlock함수 생성
-> 블럭의 좌표 중 제일 작은 (minY, minX)를 (0, 0)으로 맞추고 나머지 좌표들을 min값에 따라 상대적으로 조정
- game_board, table을 각각
findBlocks->sortBlock에 넣어서 정렬된 블럭 모음으로 만들기
- 정렬된
sortTableBlocks을 기준으로 usedList를 만든 후 False로 초기화
- 정렬된
sortGameBoardBlocks을 for문으로 돌며, 각 game_board 속 빈공간이 table의 블럭과 일치하는지 확인
->sortTableBlocks도 for문을 돌며 각 game 빈공간과 각 table 블럭을 비교 (이때rotateBlock를 통해 회전시켜가며 확인)
- 일치하는 블럭의 칸 수를 result에 누적시키다가 최종적으로 result 반환
