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.2

백준 14889 스타트와 링크

# 14889 스타트와 링크

# dfs = 가능한 팀의 경우의 수를 모두 추출한다. 
def dfs():
    if len(R) == (N//2):
        start.append(R[:])
        link.append(list(set(num) - set(R[:])))
    for i in range(1,N+1):
        if i > R[-1]:
            R.append(i)
            dfs()
            R.pop()

M = []
N = int(input())
for i in range(N):
    M.append(list(map(int, input().split())))
num = [i for i in range(1,N+1)]

# 모든 경우에 팀 안에 1번이 들어있으므로 1번이 들어간 모든 경우의 수를 출력하면 된다.
R = [1]
start = []
link = []
dfs()

# result = 스타트팀과 링크팀 점수차를 저장하는 리스트
result = []

for i in range(len(start)):
    start_sum = 0
    link_sum = 0
    for j in range(N//2):
        for _ in range(N//2):
            start_sum += M[start[i][j]-1][start[i][_]-1] 
            link_sum += M[link[i][j]-1][link[i][_]-1]
    result.append(abs(start_sum -link_sum)) 
print(min(result))

처음에 함수 dfs()에서 R을 저장하려고 할 때, 저장해서 출력하면 빈 리스트만 나와서 당황했었다.

그 이유는 R의 요소를 저장한게 아니라 R 자체를 저장한 것이라 pop()이 되어서 그렇다는데 정확하게 이해하지 못했다.

아무튼 그걸 해결하기 위해서 R[:]을 취해서 요소를 저장해줬더니 문제를 해결할 수 있었다.

문제풀이의 아이디어는 일단 팀으로 만들 수 있는 모든 경우의 수를 찾아내고

또 그팀 안에서 점수를 낼 수 있는 모든 조합을 계산한 다음, 두 팀 간 점수 차의 절댓값을 구하면 된다고 생각했다.

dfs() 함수를 통해서 가능한 start와 link 팀의 경우의 수를 구했고 각 인덱스는 서로 대비된다.

start팀에 start[1]의 요소가 배정되면 link팀에는 전체 팀원에서 start[1]을 뺀 link[1]이 배정된다.

그리고 경우의 수를 구할 때 R이라는 임의의 리스트에 1을 넣어둔 이유는 어떤 경우라도 1번은 둘 중 한 팀에

무조건 들어가 있어야 하기 때문에 그냥 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.04

백준 1012 유기농 배추

# 1012
import sys
sys.setrecursionlimit(10**6)


def DFS(x,y):
    if 0 > x or x >= N or 0 > y or y >= M:           
        return False
    
    if arr[x][y] == 1:         
        arr[x][y] = 0                                  
        DFS(x-1,y)
        DFS(x,y+1)
        DFS(x+1,y)
        DFS(x,y-1)
        return True


T = int(input())    #테스트 케이스
    
for i in range(T):
    M, N, K = map(int, input().split())
    
    arr = [[0]*M for i in range(N)]  # 배추밭의 2차원 배열
    R = 0                            # 배추흰벌레 마리 수
       
    for j in range(K):
        a, b = map(int, input().split())
        arr[b][a] = 1

    for ii in range(N):
        for jj in range(M):
            if DFS(ii,jj) == 1: # 배추밭의 좌표(0,0)부터 끝까지 확인
                R += 1
    print(R)

편법?

import sys
sys.setrecursionlimit(10**6)

서버의 재귀 깊이를 늘려주는 함수를 사용해서 간신히 풀었다.

아무래도 DFS 함수의 재귀로 불러오는 게 너무 많아서 그런 듯하다.

재귀를 줄이고 반복문을 늘리는 함수를 짜 봐야겠다.

#2667 

N = int(input())
P = [list(map(int,input())) for i in range(N)]

def DFS(x,y):
    global R
    if 0 > x or x >= N or 0 > y or y >= N:
        return False
    
    if P[x][y] == 1:
        R += 1
        P[x][y] = 0
        DFS(x-1,y)
        DFS(x,y+1)
        DFS(x+1,y)
        DFS(x,y-1)
        return True
    return False           # 지워도 됨
        

arr = []                   # 단지 내 아파트 숫자를 저장
R = 0                      # 단지 내 아파트 숫자
for i in range(N):
    for j in range(N):
        if DFS(i,j) == 1:
            arr.append(R)
            R = 0
print(len(arr))
for i in sorted(arr):
    print(i)

DFS(Depth First Search)란?

DFS란 깊이 우선 탐색으로 불리며 그래프 탐색의 한 종류이다.

루트 노드나 지정된 노드에서 시작하여 그 노드의 최대 깊이까지 탐색한 다음

더 이상 탐색 불가능하면 부모 노드로 돌아와 다른 노드로 탐색을 진행한다.

알고리즘 진행 모습은 이렇다.

이처럼 최고 깊이까지 탐색한 다음 더 이상 진행할 곳이 없으면

부모 노드로 돌아와 노드로 탐색을 진행한다.

순서의 2, 5, 9 노드로 순서로 진행하는 것은 조건을 어떻게 주느냐에 따라 다르다.

예를 들어 노드에 주어진 값이 가장 작은 것부터 탐색하거나

큰 값부터 탐색하는지 주어진 조건에 따라 탐색 순서는 바뀔 수 있다.

DFS 알고리즘 문제는 스택자료구조나 재귀 함수를 사용한다.

이때 가장 중요한 점은 방문한 노드를 방문처리하는 것이다.

방문처리하지 않으면 같은 곳을 계속 방문할 가능성이 있다.

최근 DFS와 BFS 자료구조 문제를 풀려고 시도하는데 구현에 어려움이 있어서 

개념을 정리 후에 다시 풀어보려고 작성한 글입니다.

2021.12.29

백준 2606 바이러스

#2606

F = int(input())
C = int(input())
W = [[] for i in range(F+1)]

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

arr = []
def DFS(x):
    arr.append(x)
    for i in W[x]:
        if i not in arr:
            DFS(i)
DFS(1)    
print(len(arr)-1)            # 1을 제외 갯수를 세어야 하기 때문     

DFS 함수를 정의하는데 조금 문제가 있었다.

처음에는 return을 사용해서 재귀적으로 만들려고 했는데

오류가 뜨거나 값이 제대로 안 나오거나 그랬는데

return 할 값이 없어서 그런 듯하다.