Coding 공부

def Innerbound(x,y):
    if 0<=x<N and 0<=y<M:
        return True
    else:
        return False

def dfs(idx,bit,total):
    global result
    if bit == 2**(N*M)-1:
        result = max(result,total)
        return
    else:
        if 2**idx&bit:
            dfs(idx+1,bit,total)
        else:
            x,y = idx//M, idx%M
            nx,ny = x,y
            temp_bit = bit
            temp_num = 0
            while Innerbound(nx,ny):
                if visited[nx][ny]:
                    next_idx = nx*M + ny
                    visited[nx][ny] = False
                    temp_bit = temp_bit|(2**next_idx)
                    temp_num = temp_num*10 + arr[nx][ny]
                    nx = nx + 1
                    ny = ny
                else:
                    break
            for rx in range(nx-1,x-1,-1):
                dfs(idx+1,temp_bit,total + temp_num)
                temp_num = temp_num//10
                next_idx = rx*M + y
                temp_bit = temp_bit^(2**next_idx)
                visited[rx][y] = True
            nx,ny = x,y
            temp_bit = bit
            temp_num = 0
            while Innerbound(nx,ny):
                if visited[nx][ny]:
                    next_idx = nx*M + ny
                    visited[nx][ny] = False
                    temp_bit = temp_bit|(2**next_idx)
                    temp_num = temp_num*10 + arr[nx][ny]
                    nx = nx
                    ny = ny + 1
                else:
                    break
            for ry in range(ny-1,y-1,-1):
                dfs(idx+1,temp_bit,total + temp_num)
                temp_num = temp_num//10
                next_idx = x*M + ry
                temp_bit = temp_bit^(2**next_idx)
                visited[x][ry] = True


N,M = map(int,input().split())

arr = [list(map(int,list(input()))) for _ in range(N)]

visited = [[True for _ in range(M)] for _ in range(N)]
result = 0
dfs(0,0,0)
print(result)

처음에 모든 경우들을 각각 하나씩 그려보면서 dfs를 해주었다.

가로 혹은 세로로 최대한 세울 수 있는 직사각형을 그려주고 그때부터 dfs를 하고 하나씩 내려주면서 dfs를 해주었다.

이 방식은 오래걸리는 방식이였고, 다른 사람들의 풀이를 보고 다시 푼 방식은 다음과 같다.

N,M = map(int,input().split())

arr = [list(map(int,list(input()))) for _ in range(N)]
result = 0
# 0은 가로인걸로 1은 세로인걸로 판별
for bit_shape in range(2**(N*M)):
    total_sum = 0
    for x in range(N):
        sub_sum = 0 # 작은 단위의 SUM
        for y in range(M):
            idx = x*M + y
            if not bit_shape & (1<<idx):
                sub_sum = sub_sum*10 + arr[x][y]
            else:
                total_sum += sub_sum
                sub_sum = 0
        total_sum += sub_sum
    
    for y in range(M):
        sub_sum = 0
        for x in range(N):
            idx = x*M + y
            if bit_shape & (1<<idx):
                sub_sum = sub_sum*10 + arr[x][y]
            else:
                total_sum += sub_sum
                sub_sum = 0
        total_sum += sub_sum
    result = max(result,total_sum)
print(result)

이 방식은 모든 경우를 먼저 구하는 거다. 이 문제는 최대 16개의 칸을 가지는 것이다.

이것을 비트로 표현해서 0이면 가로로 그려진 직사각형 1이면 세로인 직사각형으로 구분을 해주는것이다.

그러면 우리는 2**(N*M)의 경우의 수를 가질수 있다. 최대 65536가지이므로, 빠르게 구할 수 있다.

비트로 현재 종이조각의 상태를 구분하고, 그 상태에 맞게 숫자를 세서 최대값을 구하면 된다.

import heapq

def solution(n, start, end, roads, traps):
    answer = 0
    INF = float('inf')
    dp = [[INF for _ in range(n+1)] for _ in range(1<<len(traps))]
    traps_index ={value:ind  for ind,value in enumerate(traps) }
    node_list = []
    graph =[[] for _ in range(n+1)]

    for road in roads:
        x,y,pay = road
        graph[x].append([y,pay,0])
        graph[y].append([x,pay,1])

    heapq.heappush(node_list,(0,start,0))
    dp[0][start] = 0
    while node_list:
        cur_time,cur_node,state = heapq.heappop(node_list)
        if end == cur_node:
            answer = cur_time
            break
        if dp[state][cur_node] < cur_time:
            continue
        for next_node,pay,flag in graph[cur_node]:
            next_state = state
            if cur_node in traps:
                if next_node in traps:
                    cur_flag = ((1&(state>>traps_index[cur_node])) + 
                    (1&(state>>traps_index[next_node])))%2
                    next_state = state^(1<<traps_index[next_node])
                else:
                    cur_flag = (1&(state>>traps_index[cur_node]))
            else:
                if next_node in traps:
                    cur_flag =  (1&(state>>traps_index[next_node]))
                    next_state = state^(1<<traps_index[next_node])
                else:
                    cur_flag = 0
            
            if cur_flag == flag:
                if dp[next_state][next_node] > cur_time + pay:
                    dp[next_state][next_node] = cur_time + pay
                    if next_node in traps:
                        heapq.heappush(node_list,(dp[next_state][next_node], next_node,next_state ))
                    else:
                        heapq.heappush(node_list,(dp[next_state][next_node],next_node,next_state))

    return answer

이 문제를 핵심은 트랩을 밟았을 때의 상태를 어떻게 저장할 것인가.

저장한 그 상태를 통해 현재 길의 상태를 어떻게 알 수 있을가인가.

이 문제는 총 4가지 경우가 있다고 볼 수 있다.

트랩이 아닌  곳 -> 트랩이 아닌곳

트랩이 아닌 곳 -> 트랩인 곳

트랩인 곳 - > 트랩이 아닌곳

트랩인 곳 -> 트랩인 곳

이렇게 총 4가지 경우가 있을거고, 각각의 상태를 구분해서, 하면 된다.

우리는 먼저 주어진 경로들을 2가지 형태로 저장해놔야한다.

원래 주어진 정방향과, 이게 뒤집혔을때 가는 역방향이다. 이걸 나는 (다음노드, 시간, 상태) 로 넣어놨다.

0이면 정방향

1이면 역방향을 의미하는 식으로 넣어놨다.

트랩은 최대10개 밖에 없고, 트랩의 상태는 비트마스킹을 통해 나타낼수있다.

그렇게 하기 위해 각각의 trap들의 index로 각자의 위치를 매핑시켜줬다.

그러면 인제부터 각위치의 비트가 1이면 해당 위치의 트랩이 활성화 된 상황이고, 비활성화일때는 0이다.

그리고 우리는 각 상태에서 다익스트라를 돌리는 것이기 때문에 최대 (2**10) * N개의 distance 테이블을 만들어놓고 탐색을 하면 된다.

원래의 다익스트라와 비슷하게 하지만, 우리는 state를 통해 현재 길을 이용할 수 있는지 없는지 판별을 해줘야한다.

한 그래프에 정방향, 역방향을 전부 넣어놨기 때문에, state를 통해서 해당 길을 이용할 수 있는지 찾아야한다.

먼저 가장 쉬운

현재 노드가 트랩이 아닐때이다.

만약 다음 노드가 트랩이 아니라면, 이 길은 항상 정방향이다. 그러므로 저장해놓길 0으로 저장해놓은 길들만 이용이 가능하다.

만약 다음 노드가 트랩이라면, state를 통해 해당 트랩이 활성화 되어있는지 판별을 하면 된다.

판별하는 방법은 현재 state를 해당 트랩의 index만큼 >> 오른쪽으로 비트 이동을 시킨다. 그리고 1과 & 연산을 하면 된다.

이게 1이면 활성화가 된 상태이고, 아니면 비활성화 상태이다.

다음은 현재노드가 트랩일때이다.

현재노드가 트랩이고, 다음노드가 트랩이 아닐때에는 위와 동일하므로 넘어가겠다.

가장 많이 고민했던, 현재노드와 다음노드가 전부 트랩일때이다.

이때는 총 4가지 경우가 생긴다.

1. 현재노드 비활성화 다음노드 비활성화

2 .현재노드 활성화 다음노드 비활성화

3. 현재노드 비활성화 다음노드 활성화

4. 현재노드 활성화 다음노드 활성화

총 4가지 경우가 생긴다.

1번의 경우는 둘다 활성화가 안되어있기 때문에 정방향인 길들만 가면된다.

2,3번은 동일하고, 한쪽만 활성화 되어있으면, 그 길은 한번 뒤집힌거기 때문에 역방향인 길들만 가면 된다.

4번은 현재노드 다음노드 전부 활성화 되어있을때이다.

이때는 이 길이 2번 뒤집힌거기 때문에, 정방향인 길들만 가면된다.

그래서 나는 

(    ( 1 & (state>>traps_index[cur_node]) ) + ( 1&( state>>traps_index[next_node]) ) )%2

2개의 상태를 더해서 2로 나눈 나머지로 해서 정방향, 역방향을 구분을 해줬다. 이 외에도 xor 연산을 해도 된다.

우리는 이렇게 해서 해당 길이 갈 수 있는 길인지 아닌지 판별을 했다.

나머지는 다익스트라와 동일하게 하면되는데, 

그리고 현재의 상태와 비교하는게 아니라, 다음의 상태와 비교를 해서 판별을 해주었다.

만약 다음 노드가 트랩이라 한다면, 그 트랩은 활성화가 된 상태인거고, 그때 최소값으로 들어가야한다고 생각했다

그래서 각 현재 시간과 다음노드까지 걸리는 시간은 현재 state가 아닌, 만약 다음노드가 트랩이라면, 트랩의 상태에 따라, 변화된 state로 비교를 해서 구현을 했다.

import sys

input = sys.stdin.readline

def dfs(state,order_cnt):
    global result
    if order_cnt >= P:
        result = min(result,dp[state])
        return
    else:
        if dp[state] > result:
            return

        else:
            for cu_node in range(N):
                if state & 1<<cu_node:
                    for next_node in range(N):
                        if not state & 1<<next_node and dp[state|1<<next_node] > dp[state] + arr[cu_node][next_node]:
                            dp[state|1<<next_node] = dp[state] + arr[cu_node][next_node]
                            dfs(state|1<<next_node,order_cnt+1)



N = int(input())


arr = [list(map(int,input().split())) for _ in range(N)]


state_string = input()
state = 0
P = int(input())
order_cnt = 0
stack = []
result = float('inf')
for i in range(N):
    if state_string[i] == 'Y':
        state += 1<<i
        order_cnt += 1
        stack.append(i)
dp = [float('inf') for _ in range(2**N+1)]
dp[state] = 0
if order_cnt == P:
    print(0)
else:
    dfs(state,order_cnt)
    if result == float('inf'):
        print(-1)
    else:
        print(result)

재귀를 이용해서 문제를 풀었다.

먼저 비트로 각 발전소의 상태를 구분해주었다.

발전소의 위치와 비트의 위치를 동일시해서, 0번째 비트가 1이면, 0번 발전소가 켜져있는것이다.

그러므로 우리는 마지막으로 들어온 입력을 이용해 현재 발전소의 상태를 비트로 표현을 해준다.

그리고 dp라는 테이블에 발전소를 고치는 최소값을 갱신해주기 위해, 만들어두었다.

그 크기는 state의 크기이므로 2**N까지가 필요하다. 

미리 만들어놓은 상태에서 dfs 함수를 통해 재귀를 하면서 문제를 푸는데 접근을 했다.

2중 포문을 돌면서 dfs에 들어온 state를 통해, 현재 켜져있는 발전소를 구분을 해준다.

그리고 발전소가 켜져있으면 두번째 for문을 통해, 켜지지 않은 발전소를 구하고, 현재 state에서 발전소를 켰을때 비용이 더 작은 경우에

추가적으로 dfs를 하는 작업을 해주었다.

그리고 문제에 주어진 P보다 크거나 같으면 종료되도록 함수를 짰다.

import sys

input = sys.stdin.readline

def dfs(state,order_cnt):
    if dp[state] != -1:
        return dp[state]
    if order_cnt >= P:
        dp[state] = 0
        return 0
    else:
        min_value = float('inf')
        for cu_node in range(N):
            if state & 1<<cu_node:
                for next_node in range(N):
                    if not state & 1<<next_node:
                        min_value = min(min_value,dfs(state|1<<next_node,order_cnt+1) + arr[cu_node][next_node])
        dp[state] = min_value
        return dp[state]

N = int(input())


arr = [list(map(int,input().split())) for _ in range(N)]


state_string = input()
state = 0
P = int(input())
order_cnt = 0
for i in range(N):
    if state_string[i] == 'Y':
        state += 1<<i
        order_cnt += 1
dp = [-1 for _ in range(2**N+1)]
if order_cnt >= P:
    print(0)
elif order_cnt == 0:
    if P:
        print(-1)
    else:
        print(0)
else:
    result = dfs(state,order_cnt)
    if result == float('inf'):
        print(-1)
    else:
        print(result)

좀 더 깔끔한 풀이는 다음과 같다.

return 되는 값을 이용해 바로 출력이 가능하게 하는것이다.

기본 적인 원리는 같으며, 반환되는 값을 비교를 해서 최저값을 갱신을 해주는 것이다.

그리고 조건을 만족했을때에는 0을리턴하는식으로 해주는 것이다.

이 풀이가 dp라는 테이블을 좀더 생산적으로 쓰면서 풀 수 있는 방식이다.

import sys

def find_agent(agent,task):
    if agent == N:
        return 1
    
    if dp[task] != -1:
        return dp[task]

    for i in range(N):
        if not (task & 1<<i):

            temp = find_agent(agent+1,task|1<<i)*arr[agent][i]/100
            if temp > dp[task]:
                dp[task] = temp
    
    return dp[task]
input = sys.stdin.readline
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]


dp = [-1 for _ in range(2**N+1)]




find_agent(0,0)

print(dp[0]*100)

문제를 푸는방식은 다음과 같다. 

각 task를 비트로 구분을 하게 한다.

이 문제에서 최대 20개의 임무가 있으므로, 2^20으로 비트를 구분해낼수 있다.

이러한 점을 이용해, 각자리의 비트는 그와 대응되는 일을 맡는것으로 가늠할 수 있다.

그래서 우리는 재귀를 이용해, 현재까지 선택된 task에서 선택되지 않은 task를 선택해 재귀를 한뒤,

그 결과값들을 최대값으로 갱신을 해주면 되는 문제이다.

또한 중복되는 일을 방지하고자, task별로 값을 저장한뒤에 그 값이 초기값이 아니면 되돌려주는 작업을 해주었다.

from collections import deque
N, M = map(int,input().split())



lower_dict = {}
upper_dict = {}

for i in range(6):
    lower_dict[chr(ord('a')+i)] = i
    upper_dict[chr(ord('A')+i)] = i

start = []
arr = []
for x in range(N):
    input_list = list(input())
    for y in range(M):
        if input_list[y] == '0':
            start = (x,y)
    arr.append(input_list)


stack = deque()
stack.append((0,start,0))
flag = True
result = []
INF = float('inf')
dx = [-1,1,0,0]
dy = [0,0,-1,1]
visited = [[[INF for _ in range(M)] for _ in range(N)] for _ in range(64)]
visited[0][start[0]][start[1]] = 0
while stack:
    time,cur_node,state = stack.popleft()
    x,y = cur_node
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<N and 0<=ny<M:
            if arr[nx][ny] != '#' and visited[state][nx][ny] == INF:
                if arr[nx][ny] in upper_dict.keys():
                    if state & 1<<upper_dict[arr[nx][ny]]:
                        visited[state][nx][ny] = time + 1
                        stack.append((time+1,(nx,ny),state))
                elif arr[nx][ny] in lower_dict.keys():
                    visited[state][nx][ny] = time + 1
                    new_state = state | 1<< lower_dict[arr[nx][ny]]
                    visited[new_state][nx][ny] = time + 1
                    stack.append((time+1,(nx,ny),new_state))
                else:
                    if arr[nx][ny] == '1':
                        flag = False
                        result.append(time+1)
                        break
                    visited[state][nx][ny] = time + 1
                    stack.append((time+1,(nx,ny),state))
    if not flag:
        break

if flag:
    print(-1)
else:
    print(min(result))

그래프를 활용한 문제이다. 여기서 주의해야 할 점은 열쇠와 문을 열수 있는 상태를 구분하는것이다.

이 상태를 구분하기 위해 비트마스킹을 이용했다.

현재 상태에서 키가 있는 위치에 도착을 하면 OR 연산을 해서 key를 업데이트 해주고,

그리고 문에 도착을 하면 현재상태와 AND 연산을 해서 True가 되면, 현재 문에 대응하는 열쇠를 소유하는 것으로 판별을 해서 지나갈수 있도록 만들어 주었다.

문제에서 문과 열쇠는 A~F,a~f 밖에 없으므로,

2**0 ~ 2**5 까지로 각각 a~f,A~F를 매핑시켜주면 된다.

그리고 이 전체 state의 크기는 64개이므로, visited 배열을 64*(N*M)의 크기로 미리 만들어둔다.

그리고 그 외에는 일반적인 BFS와 동일하게 해주면 된다.

이 문제는 비트 마스킹을 통해 현재 가지고 있는 키의 상태를 업데이트 해주고, 문에 도착했을때, 이 문에 대응하는 키를 소유하고 있는지를 구분해주면 되는 문제였다.

def TSP(ind,visited_city):
    if dp[ind][visited_city] != INF:
        return dp[ind][visited_city]
    if visited_city == (1<<N)-1:
        if arr[ind][0]:
            return arr[ind][0]
        else:
            return INF

    for next_city in range(N):
        if not (visited_city&1<<next_city) and arr[ind][next_city]:
            temp = TSP(next_city,visited_city|1<<next_city) + arr[ind][next_city]
            dp[ind][visited_city] = min(dp[ind][visited_city],temp)

    return dp[ind][visited_city]





N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]

INF = float('inf')
dp = [[INF]*(2**N) for _ in range(N)]

print(TSP(0,1))

from itertools import combinations

N,K = map(int,input().split())
ord_dict = {}
if K <5:
    print(0)
    exit()
elif K == 26:
    print(N)
    exit()
else:
    # 2**승으로 만들어 주기 위한 곳
    for k in range(26):
        ord_dict[chr(k+97)] = k

    K = K - 5
    comb_bits = 0
    # 무조건 있는 애들을 기본적으로 comb_bits로 만들어준다.
    for k in ['a','n','t','i','c']:
        comb_bits = comb_bits + 2**ord_dict[k]
    word_list = []


    for _ in range(N):
        # 앞뒤 고정 부분은 필요없으니 자른다.
        temp = set(list(input())[4:-4])
        word_list.append(temp)
    # 고정적으로 잇는 부분 제외하고 나머지를 뽑는다.
    combi_word = set(ord_dict.keys()) - set(['a','n','t','i','c'])
    result = 0
    for pick_words in combinations(combi_word,K):
        check_bits = comb_bits
        for pick_word in pick_words:
            # OR 연산을 해줘서 BIT 형식으로 만들어준다.
            check_bits = check_bits | 1<< ord_dict[pick_word]

        word_cnt = 0
        for word in word_list:
            for wo in word:
                # 만약에 AND 연산을 했는데 False가 나오면 그만둔다.
                if not (check_bits & 1<<ord_dict[wo]):
                    break
            else:
                word_cnt += 1
        result = max(word_cnt,result)
                
    print(result)

어렵지 않은 문제인데 python을 이용해서 풀려면 참 난감해진 문제였다. 조합을 잘 짜면, 시간을 넘지않을수도 있지만, 

시간초과에 걸리는 경우가 많았다.

그래서 조합을 구하는 방식을 비트마스킹을 통해 만들었따. 2**(k)승의 형태로 만들어주고, and 연산을 해서 우리가 만든 조합에 포함되어있는지 아닌지 확인하는 방식이다.

from itertools import combinations

N,K = map(int,input().split())
ord_dict = {}

for k in range(26):
    ord_dict[chr(k+97)] = k

K = K - 5
if K <0:
    print(0)
    exit(0)
else:
    origin_word = set(['a','n','t','i','c'])
    word_bit_list = list()
    combination_word = set()
    answer = 0
    for _ in range(N):
        temp = set(list(input())[4:-4]) - origin_word
        if len(temp) == 0:
            answer += 1
        elif len(temp) <=K:
            word_bit = 0
            for w in temp:
                word_bit = word_bit + 2**ord_dict[w]
            word_bit_list.append(word_bit)
            combination_word |= temp

    word_lens = len(combination_word)
    if K > word_lens:
        K = word_lens
    chk_cnt = 0
    for pick_words in combinations(combination_word,K):
        cnt = 0
        temp = 0
        for pick_word in pick_words:
            temp = temp + 2**ord_dict[pick_word]
        for word_bit in word_bit_list:
            if word_bit & temp == word_bit:
                cnt += 1

        chk_cnt = max(chk_cnt,cnt)

    print(answer + chk_cnt)

위의 방식보다 훨씬 빠른 방식이다. 이 방식은 기본적인 컨셉은 비슷하다.

하지만 2가지가 다르다.

첫번째는 전체 알파벳 26개중에서 K개를 뽑던거에서 고정적으로 들어간 a,c,i,n,t를 무조건 뽑는다고 생각하고,

그리고 주어진 단어들에 있는 단어들 중에서 나머지 K-5개를 뽑는것이다.

두번째는 각 단어들의 BIT를 비교했던것에서 단어 전체의 bit를 저장해준뒤, 우리가 만든 combination bit와 and 연산을해서, 원래 word_bit가 유지되는지 확인을 해주는 방식이다.

이러한 방법을 통해 시간을 줄일 수 있다.