[DFS/BFS] 모음_코딩테스트 고득점 Kit

타겟 넘버 (level2)

링크텍스트

#BFS 풀이
def solution(numbers, target):
    answer = 0
    leaves = [0]
    for num in numbers:
        tmp = []
        for parent in leaves:
            tmp.append(parent + num)
            tmp.append(parent - num)
        leaves = tmp
    for leaf in leaves:
        if leaf == target:
            answer += 1
    return answer

게임 맵 최단거리 (level2)

링크텍스트

#게임 맵 최단거리 코드
def solution(maps):
n, m = map(int, input().split())
graph = []
for i in range(n):
	graph.append(list(map(int, input())))

def dfs(x, y):
	if x <= -1 or x >= n or y >= -1 or y >= m:
    	return False
    if graph[4][5] == 0 and graph[4][5] == 0 and graph[5]][4] == 0
    	return False
    if graph[x][y] == 1:
    	graph[x][y] = 1
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)
        return True
   	return False


result = 0
min_result = min(result)
for i in range(n):
	for j in range(m):
    	if dfs(i, j) == True:
        	result += 1
min_result = min(result)
print(min_result)

네트워크 (level 3)

개인적으로 백준 연구소, 바이러스 등
DFS 문제 활용도 높음

i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현

링크텍스트

def solution(n, computers):            
    
    def DFS(i):
        visited[i] = 1
        for a in range(n):
            if computers[i][a] and not visited[a]:
                DFS(a)      
                
    answer = 0
    visited = [0 for i in range(len(computers))]
    for i in range(n):
        if not visited[i]:
            DFS(i)
            answer += 1
        
    return answer

def dfs(n, computers, start, visited):
	visited[start] = True
    
    for i in range(0, n):
    	if(visited[i]==False and computers[start][i]==1):
        	visited = dfs(n, computers, i, visited)
    return visited
    
def solution(n, computers):
	visited = [False] * n
    answer = 0
    
    for start in range(0, n):
    	if(visited[start] == False):
        	dfs(n, computers, start, visited)
            answer += 1
            
    return answer

단어 변환

링크텍스트
BFS 활용

from collections import deque


def solution(begin, target, words):
    answer = 0
    q = deque()
    q.append([begin, 0])
    V = [ 0 for i in range(len(words))]
    while q:
        word, cnt = q.popleft()
        if word == target:
            answer = cnt
            break        
        for i in range(len(words)):
            temp_cnt = 0
            if not V[i]:
                for j in range(len(word)):
                    if word[j] != words[i][j]:
                        temp_cnt += 1
                if temp_cnt == 1:
                    q.append([words[i], cnt+1])
                    V[i] = 1
                    
    return answer

DFS 활용

def solution(begin, target, words):
    ans = 0
    tmp = [begin]
    visited = [0 for _ in words]

    if target not in words:
        return 0

    while tmp:
        stack = tmp.pop()
        if stack == target:
            return ans      # dfs 탐색 후 최종 answer 리턴
        for i in range(len(words)):
            cnt = 0
            for j in range(len(words[i])):
                if words[i][j] != stack[j]:  # 모든 단어 길이 같으므로 이렇게 체크
                    cnt += 1
            if cnt == 1:        # words[i] 체크해서 스펠링 하나만 다를 경우 체크
                if visited[i] == 1:  # 방문한 경우
                    continue
                else:
                    visited[i] = 1   # 방문 안 한 경우
                tmp.append(words[i])
        ans += 1
    return ans

아이템 줍기

링크텍스트

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    
    # 제한사항에서 모든 좌표값은 1 이상 50 이하라고 했고 2배의 좌표를 그려야 하므로 102*102 크기의 2차원 배열 선언
    field = [[-1] * 102 for i in range(102)]
    
    # 직사각형 그리기
    for r in rectangle:
    	# 모든 좌표값 2배
        x1, y1, x2, y2 = map(lambda x: x*2, r)
        # x1부터 x2, y1부터 y2까지 순회
        for i in range(x1, x2+1):
            for j in range(y1, y2+1):
            	# x1, x2, y1, y2는 테두리이므로 제외하고 내부만 0으로 채움
                if x1 < i < x2 and y1 < j < y2:
                    field[i][j] = 0
                # 다른 직사각형의 내부가 아니면서 테두리일 때 1로 채움
                elif field[i][j] != 0:
                    field[i][j] = 1
                    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    # 큐에 캐릭터 출발지점 추가 & 최단거리를 적어줄 visited 배열 선언
    q = deque()
    q.append([characterX * 2, characterY * 2])
    visited = [[1] * 102 for i in range(102)]
    
    while q:
        x, y = q.popleft()
        # 도착한 곳이 아이템이 있는 장소라면 현재의 최단거리(나누기 2)를 answer로 하고 while문을 빠져나옴
        if x == itemX * 2 and y == itemY * 2:
            answer = visited[x][y] // 2
            break
        # 아니라면 상하좌우 네 방향을 체크하면서
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            # 현재 좌표가 테두리이고 아직 방문하지 않은 곳이라면 q에 추가 후 visited 최단거리로 갱신
            if field[nx][ny] == 1 and visited[nx][ny] == 1:
                q.append([nx, ny])
                visited[nx][ny] = visited[x][y] + 1
    
    return answer

여행경로

링크텍스트

from collections import deque
def solution(tickets):
    q = [0] * len(tickets)
    result = 0
    
    q = deque()
    for i in tickets:
    while q:
    	i = q.popleft(0)
    	for j in tickets:
        	if tickets[1][1] = "ICN":
            	q.popleft(1)
    		tickets[i][2] = tickets[j][1]
            	q.append(j)
               	result += 1
    return result

import collections
answer = []
graph = collections.defaultdict(list)

def dfs(s):
    while graph[s]:
        dfs(graph[s].pop(0))

    if not graph[s]:
        answer.append(s)
        return

def solution(tickets):
    
    for a,b in tickets:
        graph[a].append(b)
    for a, b in graph.items():
        graph[a].sort()
        
    dfs("ICN")

    return answer[::-1]

퍼즐 조각 채우기

링크텍스트

from collections import deque
import copy

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def rotate_a_matrix_by_90_degree(a):
    row_length = len(a)
    column_length = len(a[0])
    
    res = [[0] * row_length for _ in range(column_length)]
    for r in range(row_length):
        for c in range(column_length):
            res[c][row_length-1-r] = a[r][c]
    
    return res

def get_new_locations(location):
    new_locations = []
    for loc in location:
        x_min = int(1e9)
        x_max = 0
        y_min = int(1e9)
        y_max = 0
        for x, y in loc:
            x_min = min(x_min, x)
            x_max = max(x_max, x)
            y_min = min(y_min, y)
            y_max = max(y_max, y)
        new_locations.append([x_min, x_max, y_min, y_max])
    return new_locations

def bfs(table, q, location, n):
    while q:
        x, y  = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if table[nx][ny] == 1:
                    location.append([nx, ny])
                    table[nx][ny] = 0
                    q.append([nx, ny])
    return location

def get_piece_or_space(table, new_locations):
    pieces = []
    for x_min, x_max, y_min, y_max in new_locations:
        piece = []
        for x in range(x_min, x_max+1):
            row = table[x]
            piece.append(row[y_min:y_max+1])
        pieces.append(piece)
    return pieces

def solution(game_board, table):
    answer = 0
    n = len(table)
    for x in range(n):
        for y in range(n):
            if game_board[x][y] == 0:
                game_board[x][y] = 1
            else:
                game_board[x][y] = 0

    puzzle = []
    new_table = copy.deepcopy(table)
    for x in range(n):
        for y in range(n):
            if new_table[x][y] == 1:
                new_table[x][y] = 0
                q = deque([[x, y]])
                location = [[x, y]]
                puzzle.append(bfs(new_table, q, location, n))
                
    new_locations = get_new_locations(puzzle)
    pieces = get_piece_or_space(table, new_locations)
    empty = []
    
    for _ in range(4):
        new_pieces = []
        for piece in pieces:
            new_pieces.append(rotate_a_matrix_by_90_degree(piece))
        new_game_board = copy.deepcopy(game_board)
        for x in range(n):
            for y in range(n):
                if new_game_board[x][y] == 1:
                    new_game_board[x][y] = 0
                    q = deque([[x, y]])
                    location = [[x, y]]
                    new_location = get_new_locations([bfs(new_game_board, q, location, n)])
                    space = get_piece_or_space(game_board, new_location)[0]
                    if space in new_pieces:
                        new_pieces.remove(space)
                        for x_min, x_max, y_min, y_max in new_location:
                            for x in range(x_min, x_max+1):
                                for y in range(y_min, y_max+1):
                                    if game_board[x][y] == 1:
                                        game_board[x][y] = 0
                                        answer += 1
        pieces = new_pieces

    return answer