미경이 스터디 7/26

코변·2022년 7월 26일

백준 1697번

from collections import deque
import sys

cur_su, sister = map(int, input().split())

queue = deque([])
visited =[False]* 100001
visited[cur_su] = True
queue.append([cur_su, 0])
directions = ['+1' , '-1', '*2']
while queue:
    cur_su, time = queue.popleft()
    if cur_su == sister:
        print(time)
        sys.exit(0)
    for direction in directions:
        n_su = eval(str(cur_su) + direction)
        n_time = time +1
        if 0 <= n_su <= 100000 and not visited[n_su]:
            visited[n_su] = True
            queue.append([n_su , n_time])
print(-1)

내가 이해한 룰

가만히 있는 동생을 향해 수빈이가 -1, 1, *2 만큼 이동한다.
한번 이동할 때 마다 이동 카운트가 증가
동생과 수빈이의 위치가 같아졌을 때 카운트를 반환

문제풀이

가능한 모든 곳을 순회하므로 BFS로 접근했다.
2-1. 처음에 수빈이가 이동하는 방법 세가지를 모두 if분기문으로 처리했다.
2-2. 생각해보니 for문으로 처리하면 더 간단할 것 같아서 directions 라는 리스트에 +1 -1 *2를 담아 eval함수를 통해서 계산했다.
동생과 같은 곳에 서지 않은 곳들을 다시 방문할 필요가 없으므로 visited를 만들어 방문한 곳들을 다 방문처리 해주었다.

백준 6603번

from itertools import combinations
while True:
    try:
        selected_nums = list(map(int, input().split()[1:]))
        for lotto_num in sorted(list(combinations(selected_nums, 6))):
            print(' '.join(map(str, lotto_num)))
        print()
    except:
        break

내가 이해한 룰

주어진 숫자들 중에서 6개를 뽑을 수 있는 모든 경우의 수를 담아서 반환해라.
반환하는 리스트를 오름차순으로 정렬해라

문제풀이

첫번재 주어지는 숫자는 리스트의 길이이므로 따로 빼준다.
combination을 통해 6개를 고른 모든 경우의 수를 리스트에 담는다.
담긴 각 숫자들을 join함수를 통해서 반환해준다.

def combinations(array, num):
    result = []
    if num == 0:
        return [[]]
    
    for idx, elem in enumerate(array):
        for others in combinations(array[idx+1:],num-1):
            result.append([elem] + others)
    return result

while True:
    selected_nums = list(map(int, input().split()))
    len_of_selected = selected_nums.pop(0)
    if len_of_selected == 0:
        break
    for lotto_num in sorted(list(combinations(selected_nums, 6))):
        print(' '.join(map(str, lotto_num)))
    print()

문제풀이 - 함수제작

이렇게 풀면 간단하게 풀 수 있겠지만 아무래도 찜짐했다. 문제에서 요구하는 바가 '라이브러리를 사용해서 풀어라'는 아닐테니까
직접 combinations 함수를 만들어서 사용해보았다.
이렇게 풀어보면서 다른 사람들의 코드를 보니 dfs로도 푸는 것을 봤다.

def dfs(lotto, visited, input_nums):
    if len(lotto) == 6:
        for number in lotto:
            print(input_nums[number], end = ' ')
        print()
        return
        
    visited_now = visited[:]
    for i in range(len(visited_now)):
        if visited_now[i] ==0:
            visited_now[i] = 1
            dfs(lotto+[i], visited_now, input_nums)
            
while True:
    selected_nums = list(map(int, input().split()))
    if selected_nums[0] == 0:
        break
    len_of_selected = selected_nums.pop(0)
    visited = [0] * len_of_selected
    dfs([],visited, input_nums)
    print()