BAEKJOON : 10971, 13023, 14391, 9012

No. 10971

1. Problem

2. My Solution

• 첫 번째 방법
• itertools 모듈 permutations 함수 사용
• 10! = 3628804 개의 순열 = 473 MB -> 메모리초과

from itertools import permutations
import sys
import math

n = int(sys.stdin.readline())
city = []
res = []

for _ in range(n):
    city.append(list(map(int,sys.stdin.readline().rstrip().split())))

routes = [i+(i[0],) for i in list(permutations(range(n),n))]

for route in routes:
    sum = 0
    for i in range(n):
        if city[route[i]][route[i+1]] == 0:
            sum += math.inf
            break
        sum += city[route[i]][route[i+1]]
    res.append(sum)

print(min(res))

• 두 번째 방법
• 3628804 개의 순열을 모두 생성하지 않고 순열 생성 코드를 직접 구현하여 백트래킹 기법 적용
• Python3 시간초과, PyPy3 통과 (0.128MB, 1160ms)

import sys
import math

def sum(route):
    global res
    temp = 0
    for i in range(n-1):
        temp += city[route[i]][route[i+1]]
    temp += city[route[-1]][route[0]]
    res = min(res, temp)

def permutation(level):
    if level >= n:
        if city[arr[-1]][arr[0]] != 0:
            sum(arr)
    else:
        for i in range(n):
            if visited[i] == True:
                continue
            elif level > 0 and city[arr[level-1]][i] == 0:  # out of index 방지를 위해 level > 0 을 and 연산자 왼쪽에 배치
                continue
            else:
                visited[i] = True
                arr[level] = i
                permutation(level+1)
                visited[i] = False

n = int(sys.stdin.readline())
city = []
res = math.inf
visited = [False] * n
arr = [0] * n

for _ in range(n):
    city.append(list(map(int,sys.stdin.readline().rstrip().split())))

permutation(0)
print(res)

• 세 번째 방법
• 445MB 메모리를 사용하지만 통과됨..?
• 그냥 코드를 수행하면 시간초과지만 함수로 모든 코드를 수행하면 통과

from itertools import permutations
import sys
import math

def solution():
    n = int(sys.stdin.readline())
    city = []
    res = math.inf
    

    for _ in range(n):
        city.append(list(map(int,sys.stdin.readline().rstrip().split())))

    routes = list(permutations(range(n)))

    for route in routes:
        if city[route[-1]][route[0]] == 0:
            continue
        sum = 0
        flag = False
        for i in range(n-1):
            if city[route[i]][route[i+1]] == 0 or sum >= res:
                sum += math.inf
                flag = True
                break
            sum += city[route[i]][route[i+1]]

        if flag:
            continue

        sum += city[route[-1]][route[0]]
        res = min(res,sum)

    print(res)

solution() 

• 외판원 순회 전용 풀이방법과 DFS를 이용한 해결 방법은 추후 풀어볼 예정

3. Learned

• 함수내에서 수행하면 속도가 더 빠름 (스택오버플로우)
• 메모리의 사용량을 확인하고 싶을 때는 tracemalloc 모듈 사용(파이썬 문서)
  - 함수내에서 사용되고 해당 scope 를 벗어나면 없어지거나 찌꺼기 메모리만 남음
  
• 코드를 제출하기전에 time 모듈로 시간 체크하고, tracemalloc 모듈로 메모리 체크하는 습관 들이기

No. 13023

1. Problem

2. My Solution

• DFS 알고리즘을 이용하여 문제 해결
• A -> B -> C -> D -> E 처럼 5명이 쭉 알고있다면 (깊이가 5라면) 1출력 아니면 0 출력
• 깊이가 5인 순간 바로 1을 출력하고 exit()
• 모든 사람을 기준으로 해당 관계가 존재하는지 판단하기 위해서 매번 visited 를 초기화 시킴

import sys
sys.setrecursionlimit(10**8)

def dfs(v,level, visited):
    visited[v] = True
    level += 1
    
    if level >= 5:
        print(1)
        exit()

    for u in range(n):
        if u in friendship[v] and visited[u] != True:
            dfs(u,level, visited)
    

n, link = map(int,sys.stdin.readline().rstrip().split())
friendship = [[] for _ in range(n)]
visited = [False] * n

for _ in range(link):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    friendship[a].append(b)
    friendship[b].append(a)

for i in range(n):
    visited_copy = visited.copy()
    dfs(i,0,visited_copy)

print(0)

3. Others' Solutions

• 위에 코드는 아래에서 빨간색 경로로 가게되면 깊이가 5가되지 않아서 다시 돌아간뒤 파란색 경로로 탐색해야 되지만 빨간색 경로 때 True 로 설정했기 때문에 파란색 경로로 수행될 수 없음 따라서 다시 False로 초기화하는 작업이 필요함
  

• for 문에서 dfs(i,0) 을 수행한 뒤에 해당 노드가 탐색되도록 하기 위해서 vistited[i] = False 수행

import sys

def dfs(v,level):
    visited[v] = True
    level += 1

    if level >= 5:
        print(1)
        sys.exit()

    for u in friendship[v]:
        if visited[u] == False:
            dfs(u,level)
            visited[u] = False
    
n, m = map(int,sys.stdin.readline().rstrip().split())
friendship = [[] for _ in range(n)]
visited = [False] * n

for _ in range(m):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    friendship[a].append(b)
    friendship[b].append(a)

for i in range(n):
    dfs(i,0)
    visited[i] = False

print(0)

3. Learned

• PyPy3 에서 setrecursionlimit() 이 적용되긴 하지만 이에따른 메모리가 생겨남. 메모리 제한이 512MB 일때 setrecursionlimit(10**5) 까지만 수행되고 6부터는 메모리초과
• BFS 알고리즘은 적용할 수 없음. B에서 시작한다고 가정했을 때 빨간색 경로는 DFS로 깊이 5에 도달할 수 있지만 BFS 는 깊이 3까지만 가게됨

No. 14391

1. Problem

2. Others' Solution

• 비트마스크 알고리즘을 이용하여 문제 해결
• n*m 개 bit 만큼 이진수 정수를 표현할 수 있음
• 여기서는 포함 여부가 아닌 (모두 다 포함됨) 0 이면 가로, 1 이면 세로로 판단
• k = i * m + j ( i 마다 행이 바뀌고 j 마다 열이 바뀜 )
• 참고 블로그

import sys

n, m = map(int,sys.stdin.readline().rstrip().split())
paper = []
res = 0

for _ in range(n):
    paper.append(list(map(int,list(sys.stdin.readline().rstrip()))))

for bit in range(1 << n*m):
    sum = 0

    # 가로 찾기
    for i in range(n):
        temp = 0
        for j in range(m):
            k = i * m + j
            if bit & (1 << k) == 0:                 # 가로라면
                temp = temp * 10 + paper[i][j]      # 숫자 뒤에 붙이기 위해 원래 존재하는 수에 *10 한뒤 덧셈
            else:                                   # 세로라면
                sum += temp
                temp = 0  
        sum += temp

    # 세로 찾기
    for j in range(m):
        temp = 0
        for i in range(n):
            k =  i * m + j
            if bit & (1 << k) != 0:                # == 1 하면 버그발생 
                temp = temp * 10 + paper[i][j]
            else:
                sum += temp
                temp = 0
        sum += temp
    
    res = max(res, sum)

print(res)                                   

3. Learned

• 비트마스크에서 해당 원소가 모두 포함되는 경우에는 0과 1로 다른 정보를 표현할 수 있음
• n 개의 bit로 표현할 수 있는 최댓값은 2^n -1
  (n 개의 bit로 표현할 수 있는 최댓값은 n개 모두 1인경우이고 가중치는 0부터 시작하기 때문에 최대 가중치는 n-1 임. 따라서 2진수의 n 가중치 bit가 1이고 나머지가 0인 이진수에서 -1을 하면 n-1 가중치부터 0까지 모두 1인 bit가 만들어짐)

No. 9012

1. Problem

괄호 문제 복습

2. My Solution

• 첫 번째 방법

import sys

def solution():
    test_n = int(sys.stdin.readline())

    for _ in range(test_n):

        stack = []
        flag = False

        for i in (list(sys.stdin.readline().rstrip())):
            if i == '(':
                stack.append(i)
            elif stack:
                stack.pop()
            else:               
                flag = True
                
        
        if stack or flag == True:   # ')' 먼저 나온경우 또는 스택에 '(' 가 남아있는 경우
            print("NO")
        else:
            print("YES")
                
solution()

• 두 번째 방법

import sys

def solution():
    
    stack = []

    for i in (list(sys.stdin.readline().rstrip())):
        if i == '(':
            stack.append(i)
        elif stack:
            stack.pop()
        else:               
            print("NO")
            return
            
    if stack:  
        print("NO")
    else:
        print("YES")

test_n = int(sys.stdin.readline())
for _ in range(test_n):
    solution()