DFS/BFS 문제 유형의 한 문제입니다.

왜 우선 탐색 문제일까 고민하던 중에 스터디원이 준 힌트를 듣고 풀이 방법을 알아냈습니다.

트리로 보면 리프 노드를 구한다음 타깃과 같은 값을 가진 노드의 개수를 구하면 됩니다.

아래의 그림처럼 생각할 수 있습니다.

예를 들어 배열로 [4, 1, 2, 1]이 들어오고 타겟 넘버가 4일 경우의 수는 두 가지입니다.

import java.util.*;
class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        Queue<Integer> answerList = new LinkedList<Integer>();
        answerList.add(0);
        
        for(int i: numbers){
            int size = answerList.size();
            for(int k = 0; k < size; k++){
                int pop = answerList.poll();
                answerList.add(pop + i);
                answerList.add(pop - i);
            }
        }
        
        for(int i :answerList){
            if(i == target){
                answer += 1;
            }
        }
        
        return answer;
    }
}

그래프를 그리면서 탐색할 Queue를 하나 만들어 주고 루트 노드로 0을 넣어줬습니다.

이후로는 해당 레벨의 갯수 만큼 반복하며 하위 노드를 만들고 부모 노드를 삭제하는 것을 반복합니다.

마지막에는 큐에 리프 노드의 숫자들만 남게 됩니다.

2022.01.14

백준 1697 숨바꼭질

# 1697 숨바꼭질
from collections import deque

N, K = map(int,input().split())

# 리스트 인덱스에 점으로 이동하는 시간을 저장하기 위해서 arr생성
# x-1이 더 빠른 경우도 있기 때문에 가장 큰 값에서 +2해준다.
if N >= K:
    arr = [0] * (N+2)
else:
    arr = [0] * (K+2)
    
def bfs(x):
    queue = deque()
    queue.append(x)
    arr[x] = 0
    if x == K:   # N == K 같은 경우 0 리턴
        return 0
    while queue:
        a = queue.popleft()
        dx = [1,-1,a]
        for i in range(3):
            nx = a + dx[i]
            if 0 <= nx < len(arr) and arr[nx] == 0:
                queue.append(nx)
                arr[nx] = arr[a] + 1
bfs(N)
print(arr[K])

x와 K 값이 같을 때 값을 지정해주는 것과 arr의 범위를 잘 못 정해줘서

문제가 무엇일까 하고 한참을 쳐다보았었다.

백준 7569 토마토

from collections import deque

m,n,h = map(int, input().split())

graph = []

for _ in range(h):
    graph.append([ list(map(int,input().split())) for _ in range(n) ])

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

queue = deque()

def bfs():
    for i in range(h):
        for j in range(n):
            for k in range(m):
                if graph[i][j][k] == 1:
                    queue.append((i,j,k))
    
    while queue:
        x,y,z = queue.popleft()
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]

            if 0 <= nx < h and 0 <= ny < n and 0 <= nz < m :
                if graph[nx][ny][nz] == 0 :
                    queue.append((nx,ny,nz))
                    graph[nx][ny][nz] = graph[x][y][z] + 1

bfs()
R = []
for i in range(h):
    for j in range(n):
        if 0 in graph[i][j]:
            R.append(0)
        else:
            R.append(max(graph[i][j]))
if 0 in R:
    print(-1)
else:
    print(max(R)-1)

처음에 2차원 배열로 풀려다가 상자 층이 넘어가는 것을

인접면으로 탐색하는 걸 해결 못해서 포기했다.

결국 3차원으로 풀었는데 어제 풀었던 7576번 문제와 똑같고

차원이 하나 추가돼서 좌표설정만 헷갈리지 않으면 됐다.

2022.01.11

백준 7576 토마토

#7576
from collections import deque

M, N = map(int, input().split())
arr = []
for i in range(N):
    arr.append(list(map(int,input().split())))
    
def BFS(graph):
    queue = deque()
    for i in range(N):
        for j in range(M):
            if arr[i][j] == 1:
                queue.append((i,j)) #토마토가 여러개 있을 때를 해결
    
    dx = [0,0,-1,1]
    dy = [-1,1,0,0]
    while queue:
        a, b = queue.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if arr[nx][ny] == 0:
                    queue.append((nx,ny))
                    arr[nx][ny] = arr[a][b] + 1
            
BFS(arr)
R = []
for i in range(N):
    if 0 in arr[i]:
        R.append(0)
    else:
        R.append(max(arr[i]))
if 0 in R:
    print(-1)
else:
    print(max(R)-1)       

토마토가 여러 개 존재하면 어떻게 풀지?라는 의문을 반복문을 통해 해결했더니 

다른 BFS 문제와 별다를 게 없었다. 또 다른 점이라면 출력 조건이 좀 많다는 점?

2022.01.10

백준 2178 미로 탐색

# 2178
from collections import deque

N, M = map(int, input().split())
arr = [list(map(int, input())) for i in range(N)]

def BFS(x,y):
    dx = [0,-1, 1, 0]
    dy = [1, 0, 0, -1]
    queue = deque()
    queue.append((x,y))
    
    while queue:   
        a, b = queue.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            
            if 0<=nx<N and 0<=ny<M:
                if arr[nx][ny] == 1:
                    queue.append((nx,ny))
                    arr[nx][ny] = arr[a][b] + 1

BFS(0,0)
print(arr[N-1][M-1])

칸을 지나면 그다음 칸을 +1 해주는 아이디어로 풀었다.

방문처리를 안해서 중복 방문하기 때문에 다른 좌표들은 문제가 있지만

끝 좌표는 더이상 진행할 곳이 없어서 문제없다.

# 2178 방문처리 한 코드
from collections import deque

N, M = map(int, input().split())
arr = [list(map(int, input())) for i in range(N)]
visited = [[False]*M for i in range(N)]

def BFS(x,y):
    dx = [0,-1, 1, 0]
    dy = [1, 0, 0, -1]
    queue = deque()
    queue.append((x,y))
    
    while queue:   
        a, b = queue.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            
            if 0<=nx<N and 0<=ny<M:
                if arr[nx][ny] == 1 and visited[nx][ny] == False:
                    queue.append((nx,ny))
                    visited[nx][ny] = True
                    arr[nx][ny] = arr[a][b] + 1

BFS(0,0)
print(arr[N-1][M-1])

방문처리 코드를 넣어도 시간이나 메모리에서 그다지 차이는 보이지 않았다.

2022.01.07

백준 2667 단지 번호 붙이기

#2667 단지번호붙이기
from collections import deque

N = int(input())
arr = [list(map(int,input())) for i in range(N)]
visited = [[False]*N for i in range(N)]  # 한 번 들른 곳은 방문처리

dx = [-1, 0, 0, 1]    # 상하좌우의 좌표를 이용하기 위해서
dy = [0, 1, -1, 0]

R = []  # 단지 내 아파트 숫자를 저장하려는 리스트

def BFS(x,y):
    queue = deque()
    queue.append((x,y)) # (x,y)로 append하면 pop할 때 두 x,y를 한 번에 꺼낼 수 있다
    num = 0             # 단지 내 아파트 숫자 세기
    if arr[x][y] == 1 and visited[x][y] == False:
        num += 1
        visited[x][y] = True
        
    while queue:
        v,b = queue.popleft()
        
        for i in range(4):
            nx = v + dx[i]
            ny = b + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if arr[nx][ny] == 1 and visited[nx][ny] == False:
                    queue.append((nx,ny))
                    visited[nx][ny] = True
                    num += 1
    return R.append(num)

for i in range(N):
    for j in range(N):  # 반복문 두개 돌려서 좌표 (0,0) 부터 (N-1,N-1)까지 확인
        if arr[i][j] == 1 and visited[i][j] == False:
            BFS(i,j)
            
print(len(R))
for i in sorted(R):
    print(i)

deque에 좌표(x,y)를 append 해서 한 번에 꺼내는 것을 몰랐다면 더욱 지저분한 코드가 되었을 것 같다.

return을 해주는 위치랑 nx,ny 범위 지정을 잘못했는데 못 찾아서 한참을 헤맸다.

DFS로 풀 때와 다른점은 좌표의 범위 제한을 while구문 안에 넣은 것과 visited를 사용한 점이다.

숙달되려면 멀었다. 더 많은 관련 문제를 풀어봐야지

2022.01.06

백준 2606 바이러스

## 2606
from collections import deque

N = int(input())
C = int(input())
arr = [[] for i in range(N+1)]        # N+1 해준 이유는 숫자 인덱싱을 맞추려고

for i in range(C):
    a, b = map(int,input().split())
    arr[a].append(b)
    arr[b].append(a)

visited = []        # 방문한 컴퓨터 번호
def BFS(x):
    queue = deque([x])
    visited.append(x)
    
    while queue:
        v = queue.popleft()
        for i in arr[v]:
            if i not in visited:
                queue.append(i)
                visited.append(i)
                
BFS(1)
print(len(visited) -1) # 1번 컴퓨터는 제외

queue는 while 문이 핵심 같다.popleft를 통해서 나온 수를 인덱스로 사용해서 큐에 다시 삽입하고

다시 반복을 통해서 queue를 공백으로 만드는 것이 재귀를 이용하는 DFS와의 차이처럼 느껴진다.

BFS(Breadth First Search)란?

BFS란 너비 우선 탐색으로도 불리며 시작 노드부터 가장 가까운 노드들을 방문하고

멀리 떨어진 노드를 나중에 탐색하는 방법이다.

DFS가 하나의 노선을 따라 종점까지 다녀오고 다시 다음 노선의 종점까지 가는 느낌이라면

BFS는 내 친구들을 하나하나 만나고 그후에 내 친구들의 친구들을 만나는걸 반복하는 느낌이다. 

BFS의 장점

- 출발노드에서 목표노드까지 최단경로를 보장한다.

BFS의 단점

- 경로가 매우 길 경우, 많은 기억 공간을 필요하게 된다.

탐색

BFS는 선입선출인 큐(Queue) 자료구조 형태를 가졌기 때문에 우선 탐색 시작 노드를 큐에 삽입과

방문처리를 한다. 그다음 큐에서 노드를 꺼낸 후 노드의 인접 노드 중 방문처리 하지 않은 노드를

모두 큐에 삽입, 방문처리 한다. 위 과정을 반복한다.

파이썬에서는 큐 구조를 사용하기위해 collections의 deque 라이브러리를 사용한다.

from collections import deque