[프로그래머스] BFS/DFS 3문제

1. 문제 설명

타겟넘버

• Input
  • n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
  • `1+1+1+1+1 = 3
  • 1-1+1+1+1 = 3
  • 1+1-1+1+1 = 3
  • 1+1+1-1+1 = 3
  • 1+1+1+1-1 = 3`
• Output
  • 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
• Constraints
  • 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
  • 각 숫자는 1 이상 50 이하인 자연수입니다.
  • 타겟 넘버는 1 이상 1000 이하인 자연수입니다.
• Edge cases
  • 블라블라

알고리즘

• DFS

코드

def solution(numbers, target):
    n = len(numbers)
    answer = 0
    def dfs(idx, result):
        if idx == n:
            if result == target:
                nonlocal answer
                answer += 1
            return
        else:
            dfs(idx+1, result+numbers[idx])
            dfs(idx+1, result-numbers[idx])
    dfs(0,0)
    return answer

(저의 코드 아님)

• 해결방법은 도출해냈는데, 코드 구현에 앞서 멍 때림

설명

• 재귀적으로 하면 될 것 같다고 생각했다.

어려웠던 점

• DFS 구현을 어떻게 하는지 모른다.
  • 가장 큰 문제다.
• DFS, BFS 중에 무엇이 더 적합한지 의문이었다.

---

2. 문제 설명

네트워크

• Input
  • 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
• Output
  • 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오
• Constraints
  • 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
  • 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
  • i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
  • computer[i][i]는 항상 1입니다.
  • 입출력 예
• Edge cases
  • 블라블라

알고리즘

• DFS

코드

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 solution(n, computers):
    visited=[0]*n # 방문 표시 리스트
    answer=0 # 연결 성분 개수 초기화
    def dfs(pc): # dfs로 연결된 부분 쭉 탐색
        visited[pc]=1 # 방문 표시
        for idx,c in enumerate(computers[pc]): # 해당 컴퓨터에 연결된 컴퓨터 반복
            if c and visited[idx]==0:
                dfs(idx)

    for pc in range(n):      # n개의 컴퓨터에 대해 
        if visited[pc] == 0: # 방문 안했으면 
            dfs(pc)          # dfs 진행
            answer+=1        # dfs 1번 진행할때마다 +=1
    return answer

 

설명

푼 흔적

아 항상 생각 하다가 결과까지는 도달을 못하는 것 같다.

(하다보면 되려나…)

어려웠던 점

• 재귀와 visited 배열까지는 생각했는데… 인접된 노드의 인덱스를 어떻게 접근할지 생각을 못했다. → 알고보니 생각보다 단순함 (그치만 내 머리는 안단순)
• 진짜 처음봄 : enumerate
• 파이썬의 enumerate() 내장 함수로 for 루프 돌리기
• DFS 구현을 어떻게 하는지 모른다.
  • 가장 큰 문제다.
• DFS, BFS 중에 무엇이 더 적합한지 의문이었다.

3. 문제 설명

게임 맵 최단거리

• Input
•  
• Output
  • 게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.
• Constraints
  • maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
    • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
  • maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
  • 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.
  • 입출력 예
• Edge cases

알고리즘

• BFS

코드

from collections import deque

def solution(maps):
    row, column = len(maps), len(maps[0])
    queue = deque([(0, 0)])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # 상하좌우

    while queue:  # bfs 수행
        x, y = queue.popleft()
        for i in range(4):
            xx = x + directions[i][0]
            yy = y + directions[i][1]
            if 0 <= xx < len_x and 0 <= yy < len_y and maps[xx][yy] == 1:  # 접근이 가능하고 방문하지 않았던 곳이라면
                maps[xx][yy] = maps[x][y] + 1
                queue.append((xx, yy))
    return maps[-1][-1] if maps[-1][-1] > 1 else -1

설명

• queue 의 이론은 아는데, 어떻게 빠르게 python 으로 구현해야할지 몰라서 결국 검색함
• 파이썬 deque는 list와 dictionary와 거의 동일하게 생각하면 된다. 차이는 popleft의 시간 차이다. list의 경우 pop()으로 마지막 값을 꺼내는 경우 O(1) (일정한 시간) 시간이 걸리는데, pop(0)으로 가장 앞단에 값을 꺼낼때는 list 크기에 따라 읽어 오는 시간이 달라진다. O(n) 시간이 걸린다. 하지만 deque를 사용할 경우 popleft()를 사용하면 리스트의 pop(0)과 같은 기능을 주면서 걸리는 시간은 O(1)이 걸린다. pop을 사용하는 경우 말고 index로 값을 읽어 오는 경우는 리스트나 deque 모두 O(1)로 일정한 시간만 걸린다. 즉, index의 주소 값으로 바로 값을 찾는 것이다.

파이썬 deque 사용하는 이유 / popleft

어려웠던 점

• python 의 queue 사용법
• bfs 구현방법