목록분류 전체보기 (447)
For Programmer
백준 1504번 파이썬 문제풀이(특정한 최단 경로)
가중치 있는 최단경로는 우선 다익스트라를 가장 먼저 떠올리면 된다. 그러나 해당 문제는 조금 생각을 해야 하는데 v1,v2 를 무조건 지나야 한다고 되어있다. 따라서 1 -> N 까지 가는데 v1,v2를 무조건 지나야 한다고 되어 있으므로 나올 수 있는 최단경로는 1 -> v1 -> v2 -> N 이거나 1 -> v2 -> v1 -> N 일 수밖에 없다. 따라서 두가지를 구한 후 그 중 가장 짧은 거리를 출력하면 된다. import heapq import sys def dijkstra(s, des, distance): q = [] distance[s] = 0 heapq.heappush(q, (0, s)) while q: cost, cur = heapq.heappop(q) if cur == des: ret..
백준 1753번 파이썬 문제풀이(최단 경로)
단순한 다익스트라 문제이다. import heapq import sys input = sys.stdin.readline V, E = map(int, input().split()) K = int(input()) graph = [[] for _ in range(V + 1)] for i in range(E): a, b, cost = map(int, input().split()) graph[a].append((b, cost)) INF = 1e10 distance = [INF] * (V + 1) def dijkstra(s): q = [] distance[s] = 0 heapq.heappush(q, (0, s)) while q: cost, cur = heapq.heappop(q) if cost > distance[..
백준 1238번 파이썬 문제풀이(파티)
단순히 해당 문제를 풀려면 우선 X지점부터 각지점까지의 최단거리를 다익스트라로 구하고 그 후에 반복문을 돌며 각 지점에서 X까지 다익스트라로 최단거리를 구해서 그 2개의 합의 최댓값을 구하면 된다. 그러나 해당문제를 다익스트라 2번으로 굉장히 빠르게 풀 수 있는 방법이 있다. 바로 "각 지점에서 X까지 다익스트라로 최단거리를 구해서" 이부분을 단순히 그래프를 처음 입력받을 때 간선을 반대로 저장해놓으면 한번의 다익스트라로 모든 최단거리를 구할 수 있다. 즉, 반대로 뒤집어진 그래프에서 X지점에서 각지점까지의 최단거리가 결국 "각 지점에서 X까지 다익스트라로 최단거리" 가 되는 것이다. import heapq import sys input = sys.stdin.readline def dijkstra(s, ..
https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 꽤 복잡한 BFS + 시뮬레이션 혹은 다익스트라로 해결할 수 있다. 1. BFS + 시뮬레이션 from collections import deque N, M = map(int, input().split()) cheese = [list(map(int, input().split())) for _ in range(N)] visited = [[0] * M for _ in range(N)] dr = [-1, 0, 1, 0] ..
백준 9328번 파이썬 문제풀이(열쇠 ) - (bfs + 구현)
해당 문제는 비트마스킹으로 접근할려고 했으나 1= w + 2 or nr = h + 2 or miro[nr][nc] == '*' or visited[nr][nc]: continue if 'A'
백준 2098번 파이썬 문제풀이(외판원 순회 ) - (dfs + 비트마스킹 + dp)
처음에 그래프문제인줄 알고 그래프문제로 접근할려고 했더니 시간초과가 계속 발생하였다. N이 16이라 16!이기 때문에 일반 그래프의 dfs로는 해결할 수 없다. 따라서 생각할 수 있는 방식이 비트마스킹이다. 왜냐하면 방문처리를 다음과 같이 해주어야한다. N이 만약에 5라면 visited[row][0][1][2][3][4] = False 즉, 어느 행에 도착했을때 내가 지나온 노드들을 방문처리를 해주어야하는데 다음과 같이 모든 노드들을 방문처리를 해줄경우 5 ^ 6 개의 처리를 해주어야하기 때문에 N이 16이라면 16 ^ 17 이라 사실상 불가능하다. 이때 생각할 수 있는것이 비트마스킹 방문처리이다. 처음에는 단순히 각 지점(0~N - 1)에서 출발해서 각각의 거리 최솟값을 구한후 젤 작은 값을 출력하는 ..
백준 1194번 파이썬 문제풀이(달이 차오른다 가자 ) - (dfs + 비트마스킹)
간단한 기본형 dfs + 비트마스킹 문제이다. 각 열쇠를 들고있는 경우의 수를 모두 처리하기 위해 방문처리를 8차원 배열로 처리해야하는것을 비트마스킹을 사용하면 쉽게 3차원으로 해결할 수 있다. from collections import deque N, M = map(int, input().split()) maze = [input() for _ in range(N)] dr = [-1, 0, 1, 0] # 상 우 하 좌 dc = [0, 1, 0, -1] # 상 우 하 좌 st_r, st_c = 0, 0 for i in range(N): for j in range(M): if maze[i][j] == '0': st_r = i st_c = j visited = [[[False] * (1 = N or nc < ..
