Algorithm/Graph188 [파이썬] 프로그래머스 : 미로 탈출 (Lv.4) [파이썬] 프로그래머스 : 미로 탈출 (Lv.4) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 0.방향성 생각 node가 1000개, edge가 3000개로 입력이 작은 경우. trap수가 하필 10개. -> bitmask? state 2^10 * visit node 1000 = 10만 TSP처럼 dfs+dp+bitmask로 풀든가, 다익+bitmask로 풀기 -> 재귀는 실수할거같아서 다익 + bitmask 현재 노드 x와 다음 노드 nx가 있을 때, trap 유무로 4가지 케이스로 크게 분류한다. 1. 연결 리스트, 간선 cost 저장. imp.. 2023. 12. 3. [파이썬] 백준 2982 : 국왕의 방문 (골드2) [파이썬] 백준 2982 : 국왕의 방문 (골드2) 2982번: 국왕의 방문 지난주에 상그니 아라비아의 국왕 고둘라 창지즈 영사우드가 한국에 도착했다. 고둘라는 매우 중요한 사람이다. 따라서, 경찰은 그가 타고 있는 차량이 길에 진입했을 때, 그가 길에 있는 동안 www.acmicpc.net 문제 풀이 0. 방향성 생각 왕이 이동한 edge에 대해서 양방향으로 이용 불가능한 시간을 dict으로 저장 왕이 이동한 간선을 이동할 때, 시간이 겹치는지 안겹치는지 나눠서 풀이 1. 입력 from collections import defaultdict as dd import heapq as hq import sys input = lambda : sys.stdin.readline().rstrip() node,edg.. 2023. 11. 22. [파이썬] 백준 2251: 물통 (골드5) [파이썬] 백준 2251: 물통 (골드5) 2251번: 물통각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부www.acmicpc.net문제풀이 0. 방향성 생각물통에 담긴 물의 양을 튜플로 저장해서 visit set에 저장한다.BFS로 현재 물통에서 옮길 수 있는 방법 모두 탐색visit에 저장된 case중 A=0인 C를 answer set에 저장하고 출력1. 입력from collections import deque size = list(map(int,input().split())) init = (0,0,size[-1]) visit = .. 2023. 11. 21. [파이썬] 백준 2206 : 벽 부수고 이동하기 (골드3) [파이썬] 백준 2206 : 벽 부수고 이동하기 (골드3) 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 풀이 0. 방향성 생각 벽을 한개까지 부술 수 있다. 벽을 부순 상태 / 부수지 않은 상태 2가지로 나눈다. visit 배열의 차원을 하나 늘린다. 방향으로 나누는 state가 아니어서 위로 쌓는 방식으로 visit 층수를 늘린다. 1. 입력 from collections import deque import sys input = lambda: sys.stdin.readlin.. 2023. 11. 16. 이전 1 ··· 30 31 32 33 34 35 36 ··· 47 다음
