import sys
input = sys.stdin.readline
def combination(ind,len_string,combi):
if ind == len_string:
print(combi)
else:
for k in range(len_string):
if visited[k]:
temp = combi+string_list[k]
if temp not in record:
visited[k] = False
record.add(temp)
combination(ind+1,len_string,temp)
visited[k] = True
N = int(input())
for _ in range(N):
string_list = list(input().strip())
string_list.sort()
len_string = len(string_list)
visited = [True]*(len(string_list))
record = set()
combination(0,len_string,'')
from itertools import permutations
from collections import deque
def outOfrange(x,y):
if 0 > x or x >3 or y<0 or y>3:
return True
return False
def dfs(start,end,copy_board):
dp = [[-1]*4 for _ in range(4)]
dp[start[0]][start[1]] = 0
stack = deque()
stack.append((start[0],start[1]))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
while stack:
x,y = stack.popleft()
for i in range(4):
repeat = 0
while True:
nx = x + dx[i]*repeat
ny = y + dy[i]*repeat
if outOfrange(nx+dx[i],ny+dy[i]) or (repeat!=0 and copy_board[nx][ny]):
break
repeat += 1
for re in (1,repeat):
nx = x + dx[i] * re
ny = y + dy[i] * re
if outOfrange(nx,ny):
continue
if dp[nx][ny] == -1:
dp[nx][ny] = dp[x][y] + 1
stack.append((nx,ny))
if dp[end[0]][end[1]] != -1:
return dp[end[0]][end[1]]
return dp[end[0]][end[1]]
def find_command(x,y,find_card,copy_board):
dis1 = dfs((x,y),find_card[0],copy_board)
dis2 = dfs(find_card[0],find_card[1],copy_board)
return dis1+dis2
def solution(board, r, c):
answer = float('inf')
card_list = [[] for _ in range(7)]
card_numbers = set()
for x in range(4):
for y in range(4):
if board[x][y]:
card_list[board[x][y]].append((x,y))
card_numbers.add(board[x][y])
card_cnt = len(card_numbers)
for combi in permutations(card_numbers):
predict_dict = {}
for k in range(1<<card_cnt):
distance = 0
mouse_cursor_x = r
mouse_cursor_y = c
copy_board = [row[:] for row in board]
temp = ''
for ind,num in enumerate(combi):
start = int(bool((k&1<<(ind))))
end = (start+1)%2
temp += str(start)
find_card = [card_list[num][start],card_list[num][end]]
if not predict_dict.get(temp):
distance += find_command(mouse_cursor_x,mouse_cursor_y,find_card,copy_board)
predict_dict[temp] = distance
else:
distance = predict_dict[temp]
mouse_cursor_x = card_list[num][end][0]
mouse_cursor_y = card_list[num][end][1]
copy_board[card_list[num][start][0]][card_list[num][start][1]] = 0
copy_board[card_list[num][end][0]][card_list[num][end][1]] = 0
if distance > answer:
break
if answer > distance:
answer = distance
return answer+2*card_cnt
a = solution([[1,0,2,0],[6,2,4,0],[0,0,1,0],[6,0,0,4]],1,0)
print(a)
문제 자체는 BFS+순열+조합으로 간단해보였지만, 구현하는데 난이도가 컸던 문제였다.
기본 풀이 자체는 다음과 같다.
카드번호 1,2,3이 있다고 하면
1,2,3을 순열로 먼저 없앨 카드별 순서를 정해준다.
그리고 각 카드는 2장씩 있으므로, A,B 가 있다고 치면
1A->1B
1B->1A는 다를 것이다.
이 모든 경우를 돌려서 결과를 얻는 것이다.
그래서 먼저 나는 card_numbers에 이 보드에 있는 카드번호들을 저장해두고 permutations 모듈을 사용해서 순열을 만들었다 그리고 난뒤, 카드의 앞뒷면을 정해주기 위해 조합을 만들었다.
만약 우리가 카드가 3장이 있다고 하면 이 카드의 앞뒷면을 만들수 있는 가짓수는
000
001
010
011
100
101
110
111
이런식으로 총 8가지가 있을수 있다. 위의 가지수를 각비트로 봐보면 0~7까지인걸 알수 있다. 그러므로 저는 카드의 개수가 N이라고 하면, 2**N 만큼 range를 돌리고, 각 permutations으로 나오는 각각의 카드 index와 비트연산을 해서, 해당 카드의 앞뒷면의 순서를 결정해주었다.
이렇게 한뒤 현재 커서위치 -> 먼저 찾을 카드위치 -> 나중 찾을 카드위치 순으로, bfs를 돌렸다.
bfs를 돌릴때, ctrl 이동과 일반적인 한칸이동을 동시에 시행했다. 범위 밖을 나가던지, 아니면 카드가 있는 위치이던지, 그 위치까지의 길이를 기억해놓은뒤, 그 만큼을 dp라는 visited를 담당하는 행렬에 저장을해주었다. 그리고 우리가 찾는 목적지에 도착하면, return 해주는 방식으로 했다.
이렇게 bfs를 전부 돌린뒤에는 copy한 board에서 우리가 현재 뒤집은 카드들의 정보를 0으로 바꿔주고, 마우스 커서위치는 마지막 카드위치로 바꿔주는 작업을 해준다.
위 풀이 방식은 아슬아슬하게 시간을 통과한지라 여러부분에서 시간을 줄여주었다. 위에서 했듯이 bfs에서 매번 도착지점을 판별해주는 것이 첫번째 방법이었고, distance가 저장된 answer 보다 커지면 탐색을 중단해주는것도 그 방안이었다.
이렇게 구한 answer에 현재 카드의 종류의 2배만큼 더해서 출력해주면된다.
from collections import deque
import functools
def solution(board,r,c):
card_dict = [[] for i in range(7)]
card_tuple = set()
for x in range(4):
for y in range(4):
if board[x][y]:
card_dict[board[x][y]].append((x,y))
card_tuple.add(board[x][y])
card_tuple = tuple(card_tuple)
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def outOfrange(x,y):
if 0 > x or x >3 or y<0 or y>3:
return True
return False
@functools.lru_cache(maxsize=None)
def bfs(s,t,cards):
if s == t:
return 0
stack = deque()
stack.append((s[0],s[1],0))
visited = set()
while stack:
x,y,cnt = stack.popleft()
for i in range(4):
repeat = 0
while True:
nx = x + dx[i]*repeat
ny = y + dy[i]*repeat
if outOfrange(nx+dx[i],ny+dy[i]) or (repeat != 0 and board[nx][ny] in cards):
break
repeat += 1
for re in [1,repeat]:
nx = x + dx[i]*re
ny = y + dy[i]*re
if outOfrange(nx,ny):
continue
if (nx,ny) == t:
return cnt + 1
if (nx,ny) not in visited:
visited.add((nx,ny))
stack.append((nx,ny,cnt+1))
@functools.lru_cache(maxsize=None)
def find_card_short_count(cur_position,cards):
if len(cards) == 0:
return 0
min_distance = float('inf')
for pick_card in cards:
position1,position2 = card_dict[pick_card]
remain_cards = tuple(card for card in cards if card != pick_card)
direction1 = bfs(cur_position,position1,cards) + bfs(position1,position2,cards) + find_card_short_count(position2,remain_cards)
direction2 = bfs(cur_position,position2,cards) + bfs(position2,position1,cards) + find_card_short_count(position1,remain_cards)
min_distance = min(min_distance,direction1,direction2)
return min_distance
answer = len(card_tuple)*2 + find_card_short_count((r,c),card_tuple)
return answer
a = solution([[1, 0, 0, 3], [2, 0, 0, 0], [0, 0, 0, 2], [3, 0, 1, 0]], 1, 0)
print(a)
기본적인 풀이는 비슷하다. 대신 이 풀이는 위에서 복잡하게 비트연산을 통해 결정하는 것이 아닌, 재귀함수를 통해, 순열과 조합을 구현했고, functools.lru_cache를 통해 메모라이즈를 해주었다.
이 두 방식을 통해 시간이 획기적으로 줄어들었다.
이 풀이는 크게 2가지의 함수로 나뉠수 있다. find_card_short_count라는 함수와 bfs 함수이다.
bfs는 A->B까지 가는 최소 명령어를 찾아주는 것이다. 여기서 카드의 위치를 판단하는것은 cards라는 tuple을 통해, 있는지 판별을 해준다.
여기서 중요한것은 find_card_short_count라는 함수이다. 이 함수의 역할은 재귀를 통해 순열을 만드는 것이다.
cur_position은 현재 커서의 위치이고, cards는 현재 남아있는 카드들의 번호들이다.
이 cards를 반복문을 돌리면서 그 카드를 제거할 카드라 생각하고, cards에서 현재 선택한 card를 제외한 나머지 카드들을 remain_cards로 남겨준다.
위에서 설명했던 것처럼 한 카드에서도 먼저 제거할 카드를 선택을 해야한다. 그 방법으로 direction1과 direction2로 나뉘어서 해주었다.
한 카드에서 position1 과 position2가 있다고 하면 제거할 수 있는 방법은 두가지이다.
현재 커서위치 -> position1까지의 거리를 구해주고 position1 -> position2 까지의 거리를 구해준다. 그러면 마지막 커서의 위치는 position2가 되고 position2와 remain_cards를 가지고 find_card_short_count를 해주면 된다.
이런 방식으로 현재 커서 위치 -> position2 -> position1도 똑같이 해준다.
from itertools import combinations
from collections import Counter
def solution(orders, course):
answer = []
orders = list(map(sorted,orders))
for course_cnt in course:
temp = []
for order in orders:
temp += combinations(order,course_cnt)
dict_item = Counter(temp)
if dict_item:
max_value = max(dict_item.values())
max_dict = dict_item.most_common()
if max_value > 1:
for key,value in max_dict:
if value < max_value:
break
else:
answer.append(''.join(key))
answer.sort()
return answer
이 문제는 Counter와 combination 모듈을 이용해서 쉽게 구했다.
각 메뉴마다 combinations을 구해주고, 그 값들을 temp라는 리스트에 임시 저장을 해준다. 그런뒤에 Counter라는 모듈을 이용해서, 갯수를 쉽게 세준게 만들어준다.
거기서 max값을 찾고, 그 max값과 같은것들만 정답에 넣어주고 마지막에 정렬을 해준다.
def check():
global N,H
for ind in range(N):
current_ind = ind
for k in range(H):
if visited[k][current_ind]:
current_ind += 1
elif current_ind>0 and visited[k][current_ind-1]:
current_ind -= 1
if current_ind != ind:
return False
return True
def dfs(row_index,col_index,cnt,limit):
global N,H,result
if cnt > limit:
return
if check():
result = min(cnt,result)
return
for k in range(row_index,H):
if k == row_index:
search_y = col_index
else:
search_y = 0
for y in range(search_y,N-1):
if not visited[k][y] and not visited[k][y+1]:
visited[k][y] = 1
dfs(k,y+2,cnt+1,limit)
visited[k][y] = 0
N,M,H = map(int,input().split())
# H는 놓을 수 있는 개수
# M 은 가로선의 개수
# 앞은 가로선의 위치 뒤는 2개의 위치
result = float('inf')
visited = [[0]*N for _ in range(H)]
for _ in range(M):
row,node = map(int,input().split())
visited[row-1][node-1] = 1
if check():
print(0)
else:
for limit_insert_rows in range(1,4):
dfs(0,0,0,limit_insert_rows)
if result != float('inf'):
print(result)
break
else:
print(-1)
문제에서 최고로 놓을 수 있는 사다리의 개수는 3개가 최대이므로, 기본적으로 전체 사다리를 놓을 수 있는 위치를 골라서 재귀로 푸는 방식으로 해줬다. 그리고 result값이 바뀌면 break로 탈출을 해줬다.
사다리의 가로선의 정보를 node-1,node 둘 중 왼쪽인 node-1에 저장해줬다.
그리고 사다리가 놓을 수 없는 조건은 현재 위치인 [가로선][세로선] 과 [가로선][세로선+1] 위치에 전부 0이 존재하면 사다리를 놓을 수 있다고 가정했다. 그리고 난뒤 재귀함수에서 y축을 +2만큼 이동시켜줬다. 그 이유는 해당 가로선에서 내가 고른 세로선에서 사다리를 놓게 되면 세로선 과 세로선+1의 위치에는 사다리를 놓을 수 없다. 그러므로, y를 +2 해주었다.
그리고, 가로선 중에서 주어진 row_index가 같을때에만 그러고 그 다음 가로선부터는 전체 세로선에 대해서 탐색하면 된다.
이렇게 사다리를 추가해주면서, check()라는 함수를 통해, 문제에 주여진 조건인 start_index와 사다리를 통과하고 나온 index가 같은지 비교를 해줘서 True,False 값을 반환시켜주었다.
이렇게 풀었지만, 다른 사람들의 코드를 공부하고 더 나은 풀이로 나중에 고쳤다.
import sys
def check():
global N,H
for ind in range(N):
current_ind = ind
for k in range(H):
current_ind += visited[k][current_ind]
if current_ind != ind:
return False
return True
def dfs(ladder_index,cnt,limit):
global N,H,result
if limit == cnt:
if check():
result = limit
return
for ind in range(ladder_index,N*H):
row_index = ind//N
col_index = ind%N
if col_index == N-1:
continue
if not visited[row_index][col_index] and not visited[row_index][col_index+1]:
visited[row_index][col_index] = 1
visited[row_index][col_index+1] = -1
dfs(ind+2,cnt+1,limit)
if result != 4:
return
visited[row_index][col_index] = 0
visited[row_index][col_index+1] = 0
N,M,H = map(int,input().split())
# H는 놓을 수 있는 개수
# M 은 가로선의 개수
# 앞은 가로선의 위치 뒤는 2개의 위치
if M == 0:
print(0)
else:
result = 4
call = 0
visited = [[0]*N for _ in range(H)]
for _ in range(M):
row,node = map(int,sys.stdin.readline().split())
visited[row-1][node-1] = 1
visited[row-1][node] = -1
if check():
print(0)
else:
for k in range(1,4):
dfs(0,0,k)
if result != 4:
break
if result != 4:
print(result)
else:
print(-1)
기본적인 원리는 비슷하다. 하지만 몇몇 부분에서 백트래킹을 해줬다.
먼저 좌측에만 가로선의 정보를 저장했던 거에서, 좌우측에 정보를 저장해줬다. 대신 그 값을 1과 -1을 저장시켜줬다.
이전 코드에서 좌측에 있는지 우측에 있는지 판별해서 세로선의 index를 바꿔주던거에서 좀 더 깔끔하게 바꿔주었다.
그리고 매 함수마다 check를 해주던 것을 cnt == limit에 도달했을때, check를 해주었다.
또한 결과값의 기본값이 바뀌었을때 break를 해주는 곳을 여러군데 추가해줬다.
가장 크게 바뀐 것은 2중 for문을 돌리던 것을 단일 for문으로 바꿔주었다.
다음과 같이 세로선 8과 가로선 4일때를 그려보면 다음과 같이 사다리를 그릴수 있을 것이다.
여기서 각각의 교차선을 구한다고 생각하면,
다음과 같이 세로선 8* 가로선 4 만큼의 교차선이 나올 수 있다. 그러므로 문제에 주어진 N*H 만큼의 교차선이 주어질 수 있다.
이 중에서 사다리를 놓을 수 있는 교차선은 빨간색 동그라미가 쳐진 교차선 뿐이다. N번 세로선인 8번 세로선에는 그 다음 세로선이 없기 때문에 사다리를 놓을 수 없다.
그 외의 나머지 부분 교차선에 사다리를 놓는다고 생각하고 재귀함수를 돌리면 된다. 위에서 설명 했듯이 한 곳에 사다리를 놓을시, 해당 교차선 위치에서 가로로 2칸만큼 더 가야지만 사다리를 놓을 수 있다.
for ind in range(ladder_index,N*H):
row_index = ind//N
col_index = ind%N
if col_index == N-1:
continue
if not visited[row_index][col_index] and not visited[row_index][col_index+1]:
visited[row_index][col_index] = 1
visited[row_index][col_index+1] = -1
dfs(ind+2,cnt+1,limit)
if result != 4:
return
visited[row_index][col_index] = 0
visited[row_index][col_index+1] = 0
함수에서 이부분이 교차선을 나타내고, 교차선의 가로선과 세로선을 찾아내서 세로선이 마지막 위치한 것이면 넘어가고,
사다리를 놓을 수 있으면, 사다리를 놓은 뒤, 해당 index에서 +2를 해줘서 재귀함수를 해준다.
구현은 안했지만, 가능한 또 다른 방법은 사다리를 놓을 수 있는 교차선들을 전부 구해놓은 상태에서, 조합을 이용해 사다리를 1개 놓았을 때, 2개 놓았을 때, 3개 놓았을 때,를 구분하고, 고른 사다리가 문제가 없는지 판별해주고, 문제에 조여진 조건대로 시작 index와 도착 index를 같은지 판별하는 방법을 써도 될것 같다.
문제 자체는 어렵게 보이지 않았지만, 실제로 구현하는데에 어려운점이 많았고, 많이 틀렸던 문제였다.
중간중간 가능성이 없는것을 멈춰주고, 시간을 줄이는데 노력해야지 풀 수 있었던 힘들었던 문제였다.
T=int(input())
for t in range(T):
n,m=map(int,input().split(' '))
k=m-n
n_result=1
m_result=1
k_result=1
for i in range(1,m+1):
m_result*=i
for j in range(1,n+1):
n_result*=j
for p in range(1,k+1):
k_result*=p
print(int(m_result/(n_result*k_result)))
