[SW Intermediate] Stack2 -문제풀이 위주

Stack2 - 문제풀이 위주

---

문1: Forth

T = int(input())
for test_case in range(1, T + 1):
    cases = input().split()
    stack = []
    try:
        for i in range(len(cases)-1):
                if cases[i].isdigit():
                    stack.append(int(cases[i]))
                    continue
                else:
                    a = stack.pop()
                    b = stack.pop()
                    if cases[i] == '+':
                        stack.append(b+a)
                        continue
                    elif cases[i] == '-':
                        stack.append(b-a)
                    elif cases[i] == '*':
                        stack.append(b*a)
                    else:
                        if not b or not a:
                            stack.append(0)
                        else:
                            stack.append(b//a)
        res = stack.pop()
        if stack:
            print(f'#{test_case} error')
        else:
            print(f'#{test_case} {res}')
    except:
        print(f'#{test_case} error')

풀이:

후위 표기법으로 된 연산 문을 연산하기 위해서는 피 연산자를 스택에 넣어주고 연산자를 만나는 경우 스택에서 필요한 개수 만큼의 피 연산자를 Pop 하여 계산해 준다. 계산 결과는 다시 스택에 Push 해준다. 

 

---

문2: 미로

# 델타 탐색:
# 2차 배열의 한 좌표에서 4방향(혹은 8방향 등 필요 요소)의 인접 배열 요소를 탐색하는 방법
delta = [[-1, 0], [1, 0], [0, -1], [0, 1]]


def find_way():
    while stack:
        y, x = stack.pop()
        graph[y][x] = 1

        for dx, dy in delta:
            ry = y+dy
            rx = x+dx

            if 0 <= ry < n and 0 <= rx < n:
                if graph[ry][rx] == 3:
                    return 1
                if not graph[ry][rx]:
                    stack.append((ry, rx))
                    continue
    return 0


T = int(input())
for test_case in range(1, T + 1):
    n = int(input())
    stack = []
    # 미로 생성
    graph = [list(map(int, input())) for _ in range(n)]

    # 시작 점 찾기
    for y in range(n):
        for x in range(n):
            if graph[y][x] == 2:
                stack.append((y, x))
                break

    print(f'#{test_case} {find_way()}')

풀이:

dfs 를 이용해서 문제를 풀이하였다. 이미 방문한 곳은 graph[y][x] = 1 로 표시 해준다. 델타 탐색을 이용하여 경로를 탐색하게 되는데, 그래프 밖은 탐색할 수 없으므로 경계 조건을 걸어주었다. 

 

---

문3: 토너먼트 카드게임

# 5일차 - 토너먼트 카드게임


def div_group(st, ed):
    if st == ed:
        return st
    else:
        left = div_group(st, (st+ed)//2)
        right = div_group((st+ed)//2 + 1, ed)
        winner = game(left, right)
        return winner

def game(left, right):
    if card_list[left-1] == card_list[right-1]:
        return left
    elif card_list[left-1] == 1: #가위
        if card_list[right-1] == 2:
            return right
        else:
            return left
    elif card_list[left-1] == 2: # 바위
        if card_list[right-1] == 3:
            return right
        else:
            return left
    else: # 보
        if card_list[right-1] == 1:
            return right
        else:
            return left

T = int(input())
for test_case in range(1, T + 1):
    n = int(input())
    card_list = list(map(int, input().split()))

    print(f'#{test_case} {div_group(1, n)}')

풀이:

대표적인 분할 정복 문제이다. 

 

---

문4: 배열 최소 합

def find_min_sum(y, sum):
    # 값을 할당하기 위해서는 global 선언을 해야한다.
    global min_sum
    if y == n:
        if sum < min_sum:
            min_sum = sum
        return
    # 가지치기
    if sum >= min_sum:
        return
    for i in range(n):
        # 갔던 세로줄은 사용 불가하게 바꾸기
        if visited[i]:
            visited[i] = False
            find_min_sum(y+1, sum+arr[y][i])
            visited[i] = True

T = int(input())
for test_case in range(1, T + 1):
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    visited = [True for _ in range(n)]

    min_sum = 987654321
    find_min_sum(0,0)
    print(f'#{test_case} {min_sum}')

풀이:

풀이를 생각해내지 못하겠어서 가져온 풀이인데.. N까지의 조합을 찾아 가장 합이 작은 것을 출력하면 되는 문제이다. 

dfs 개념을 가지고 풀이되었다.