프로그래머스 고득점 kit 풀기 #DFS/BFS

1. 타겟 넘버

dfs로 구현하면 된다.

 

내 코드

def solution(numbers, target):
    global answer
    answer = 0
    def check(nums, depth, target):
        global answer
        if depth == len(nums):
            # 계산 후 타겟과 비교
            if sum(nums) == target:
                answer += 1
            # 카운트
            return
        else:
            check(nums, depth+1, target)
            nums[depth] = -nums[depth]
            check(nums, depth+1, target)
    check(numbers, 0, target)
    return answer

 

베스트 코드

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

 

이런 코드도 있지만.. 사실 일반적으로 떠올리기 어렵기 때문에 선호하지 않는다.

그렇지만 아름답다.

 

2. 네트워크

노드 탐색이다. 다만 입력되는 데이터의 형태가 다소 생소했다.

2차원 리스트가 주어지는데 0번 인덱스의 리스트는 0번 노드와 연결여부를 1/0으로 나타낸다.

[[1, 1, 0], [1, 1, 0], [0,0,1] 이렇게 주어진다면

0번노드는 0번노드, 1번노드와 연결되어있다.

1번노드는 0번노드, 1번노드와 연결되어있다.

2번노드는 2번노드와 연결되어있다.

-> 자기자신은 연결되어있다고 표시한다. node[i][i] 는 항상 1이다.

 

이런 식으로 입력되는 그래프 데이터를 탐색하고, 총 몇 개로 연결되는지를 카운트하면 된다.

bfs로 풀이했다.

 

내 코드

from collections import deque
def solution(n, computers):
    answer = 0
    visited = [False]*n
    def bfs(start):
        que = deque([start])
        visited[start] = True
        # print("start",start)
        while que:
            x = que.popleft()
            nx = computers[x]
            for i in range(len(nx)):
                if nx[i]==1 and not visited[i]:
                    visited[i] = True
                    print(i)
                    que.append(i)
        return 1
    for node in range(n):
        if not visited[node]:
            answer += bfs(node)
    return answer

visited라는 이름의 플래그 리스트를 만들고 노드 방문 여부를 기록한다.

이를 기준으로 노드 루프를 돌면서 방문하지 않은 노드만 다시 bfs형태로 진행하도록 한다.

bfs의 호출 횟수를 기록하면 된다.

 

플래그 : 컴퓨팅에서 플래그는 무언가를 기억하거나 약속된 신호를 남기기 위해 사용되는 미리 정의된 비트.

그래프 문제를 풀 때마다 사용하는 visitied 리스트가 이런 역할을 수행했다.

 

https://ko.wikipedia.org/wiki/%EB%B9%84%ED%8A%B8_%ED%95%84%EB%93%9C

비트 필드 - 위키백과, 우리 모두의 백과사전

 

공식적인 이름은 비트 필드인 듯 하다.

 

베스트 풀이

: 사실 베스트 풀이는 내 풀이와 비슷했다. 하지만 신기한 코드가 있어서 가져와봤다.

def solution(n, computers):
    temp = []
    for i in range(n):
        temp.append(i)
    for i in range(n):
        for j in range(n):
            if computers[i][j]:
                for k in range(n):
                    if temp[k] == temp[i]:
                        temp[k] = temp[j]
    return len(set(temp))

댓글에 적힌 바로는 플루이드-워셜 알고리즘을 사용했다고 한다.

검색해보니 다익스트라 알고리즘과 함께 최단경로를 탐색하는데 사용하는 알고리즘이라고 한다.

그래프 탐색을 조금 더 깊이있게 공부하게 된다면 알아보면 좋을 듯 하다.

 

3. 단어 변환

단어를 한 자리씩 변환하면서 목표 단어에 도달해야한다. 하지만 변환 후의 단어는 리스트 내에 존재하는 단어여야한다.

 

dfs로 풀이했다.

 

내 코드

def check(s1, s2):
    cnt = 0
    for i in range(len(s1)):
        if s1[i] != s2[i]:
            cnt += 1
        if cnt > 1:
            return False
    return True if cnt == 1 else False

def solution(begin, target, words):
    answer = [len(words)+1]
    # dfs?
    visited = [False]*len(words)
    def solve(s, depth,target):
        if s == target:
            answer[0] = min(answer[0], depth)
            return
        for i in range(len(words)):
            w = words[i]
            if not visited[i] and check(w, s):
                visited[i] = True
                solve(w, depth+1, target)
                visited[i] = False
    solve(begin,0, target)
    return answer[0] if answer[0] <= len(words) else 0

 

단어를 변경할 때 리스트에 저장되어있는 단어를 그대로 사용했다. 대신에 이 전에 단어와 한 자리만 차이나는 단어인지를 검사하는 함수를 추가로 사용했다.

 

생각보다 깔끔하게 풀려서 기뻤다.

 

베스트 코드

from collections import deque


def get_adjacent(current, words):
    for word in words:
        if len(current) != len(word):
            continue

        count = 0
        for c, w in zip(current, word):
            if c != w:
                count += 1

        if count == 1:
            yield word


def solution(begin, target, words):
    dist = {begin: 0}
    queue = deque([begin])

    while queue:
        current = queue.popleft()

        for next_word in get_adjacent(current, words):
            if next_word not in dist:
                dist[next_word] = dist[current] + 1
                queue.append(next_word)

    return dist.get(target, 0)

yield는 제네레이터라는 존재인데... 나중에 더 알아보자. (술 마신 채 쓰는 블로그라 머리아픔)

 

4. 여행경로

내 코드 (50점 맞은 코드..)

def solution(tickets):
    ways = dict()
    for t in tickets:
        prev, dest = t
        try:
            ways[prev].append(dest)
        except:
            ways[prev] = [dest]
    for r in ways.keys():
        ways[r].sort(reverse=True)
    start = "ICN"
    answer = []
    while start in ways and ways[start]:
        answer.append(start)
        start = ways[start].pop()
    answer.append(start)
    return answer

 

 

정답 코드

def solution(tickets):
    ways = dict()
    for t in tickets:
        prev, dest = t
        try:
            ways[prev].append(dest)
        except:
            ways[prev] = [dest]
    for r in ways.keys():
        ways[r].sort(reverse=True)
    start = ["ICN"]
    answer = []
    while start:
        last = start[-1]
        if last not in ways or len(ways[last]) == 0:
            answer.append(start.pop())
        else:
            start.append(ways[last].pop())
    return answer[::-1]

 

문제의 핵심은 리스트 형태로 주어지는 노드들의 관계를 딕셔너리 형태로 변경할 수 있는지, 또 그 딕셔너리를 기반으로 그래프 탐색을 진행할 수 있는지 여부라고 생각하면 된다.

 

정답코드의 형태는 스택을 활용한 DFS라고 할 수 있다.

 

재귀를 사용하는게 불편한 경우 사용하면 좋다.

 

 

내가 실수한 점이라면, while 부분을 작성할 때 설정한 조건이라고 할 수 있겠다.

스택을 사용해야 한다는 점과, 리스트에서 값을 추출하는 작업을 원활히 진행하기 위해 역정렬하지 못한게

흠인 것 같다.

 

list.pop(0)보단 list.pop()이 훨씬 빠를테니까.

 

너무 아쉽게 틀렸지만 dfs를 사용하는 새로운 방법을 알게된 것 같아 기쁘다.