Programmers / DFS / BFS 문제 모음

코딩테스트 연습 - 타겟 넘버 | 프로그래머스 스쿨 (programmers.co.kr)

def solution(numbers, target):
    n=[0]
    for i in numbers:
        num=[]
        for j in n:
            num.append(j+i)
            num.append(j-i)
        n=num
    return n.count(target)

 

 

코딩테스트 연습 - 네트워크 | 프로그래머스 스쿨 (programmers.co.kr)

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

 

 

코딩테스트 연습 - 게임 맵 최단거리 | 프로그래머스 스쿨 (programmers.co.kr)

from collections import deque
def solution(maps):
    n = len(maps); m = len(maps[0])
    visited = [[False] * m for _ in range(n)]
    q = deque()
    q.append((0, 0))
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    visited[0][0]=True
    while q:
        y, x = q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<m and 0<=ny<n and maps[ny][nx] == 1: # 맵을 벗어나지 않고 벽이 아니라면
                if not visited[ny][nx]: # 방문하지 않았다면
                    visited[ny][nx] = True
                    q.append((ny, nx))
                    maps[ny][nx] = maps[y][x]+1
    if maps[n-1][m-1]==1:
        return -1
    else:
        return maps[n-1][m-1]