본문 바로가기

프로그래밍

 (187)
백준 1504 특정 최단 경로 - 파이썬 문제. 풀이. 저번 포스트에서 풀었던 다익스트라 알고리즘에서 거쳐야하는 정점들이 추가되었다. 우선 시작 정점, v1, v2정점의 최단경로들을 구하고 start -> v1 -> v2 -> end start -> v2 -> v1 -> end 중에서 짧은 경로를 출력하면된다. 소스코드. import sys import heapq def route(start): dijkstra = [INF] * V heap = [] dijkstra[start] = 0 # 시작하는 정점 가중치는 0으로 heapq.heappush(heap,[0, start]) # 우선순위 큐에 가중치과 시작 정점 삽입 while heap: now_weight, now = heapq.heappop(heap) # 현재 테이블과 비교하여 더 가중치가 ..
백준 1753 최단경로 - 파이썬 문제. 풀이. 다익스트라 알고리즘을 숙지하고 있어야한다. https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전 컴퓨터 과학에서, 데이크스트라 알고리즘(영어: Dijkstra algorithm) 또는 다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. ko.wikipedia.org 다익스트라 알고리즘을 알지못한다면 위의 링크를 참조하면된다. 다익스트라 알고리즘은 모든 플로이드 와셜 알고리즘과 달리 해당 정점에서 모든 정점까..
백준 1707 이분그래프 - 파이썬 문제. 풀이. 이분 그래프는 연결된 정점마다 색을 칠한다고 하면 연결된 정점 끼리의 색이 서로 달라야한다. 즉 예를 들어 (1,3), (2,3) 이 연결되어 있다면 1은 빨간색 3은 파랑색 2는 빨간색 이런식으로 연결된 정점끼리의 색이 달라야한다. 풀이. from collections import deque def bfs(n): visited[n] = 1; queue=deque() queue.append(n) while queue: x = queue.popleft() for i in matrix[x]: if visited[i] == 0: visited[i] = -visited[x] queue.append(i) else: if visited[i] == visited[x]: return False retur..
백준 7562 나이트의 이동 - 파이썬 문제. 풀이. BFS를 해서 문제를 풀면된다. 나이트의 이동 범위만 잘 정해서 하면되는데 Y축으로 2칸 올라갈때는 X축이 -1, +1 만큼 움직이고 Y축으로 1칸 올라갈떄는 X축이 -2, +2 만큼 움직인다 소스코드. import sys from collections import deque def BFS(matrix, start, end): if start == end: return 1 queue = deque() queue.append([start[0], start[1]]) while queue: x, y = queue.popleft() for i in range(8): nx = x + dx[i] ny = y + dy[i] if 0
백준 1697 숨바꼭질 - 파이썬 문제. 풀이. 처음에는 그냥 굉장히 쉬울거라 생각하고 풀었는데 런타임 에러도 나고, 44퍼센트에서 틀렸다고 뜨기도해서 뭐가 문제인지 찾는데 시간이 좀 걸렸다. 우선 기본적인 BFS 방식으로 풀면되는데 주의 해야할 점은 찾아야 K가 N보다 작을 수 있다는 점을 간과하고 리스트를 K크기만큼 선언을 하였어서 실패했었고, 크기를 K, N 값중 더 큰 값으로 배열을 선언했다가 44퍼센트에서 틀렸었다. 생각해보니 찾아야할 점이 100000이여도 배열을 100000만큼만 선언하여서는 안된다 x2를 했다가 돌아오는 경우가 있기 때문에 배열 범위를 넉넉하게 잡아줘야한다. 소스코드. import sys from collections import deque def BFS(n): queue = deque() queue.app..
백준 7569 토마토 - 파이썬 문제. 풀이. 7576 토마토 문제와 3차원 배열인 점만 다르고 똑같다. 3차원 배열의 인덱스가 어떻게 이루어져 있는지 잘 생각하고 BFS에 적용을 하고 입력받은 3차원 배열에서 1의 위치를 큐에 넣고, BFS를 실행한 후 배열에 0이 있으면 -1을 출력하고 0이 없다면 배열의 최댓값에서 -1을 출력을 한다. 소스코드. import sys from collections import deque def BFS(): while queue: z, x, y = queue.popleft() for i in range(6): nx = x+dx[i] ny = y+dy[i] nz = z+dz[i] if (0
백준 7576 토마토 - 파이썬 문제. 풀이. 우선 1의 위치를 큐에 넣어주고 BFS를 실행한다. BFS 실행 후 리스트에 0이 남아있다면 -1을 출력하고 그렇지 않다면 리스트의 최댓값에서 -1을 출력한다. deque를 사용하지 않고 리스트를 사용해서 제출하면 시간초과가 난다. 소스코드. import sys from collections import deque def BFS(): while queue: x, y = queue.popleft() for i in range(4): nx = x+dx[i] ny = y+dy[i] if (0
백준 1012 유기농 배추 - 파이썬 문제. 풀이. BFS를 이용하여 1을 만나면 BFS를 실행하고 방문한곳은 0을 처리해준다 한번 BFS가 끝나면 배추흰지렁이의 갯수를 +1 해준다. 소스코드. import sys def BFS(y, x): queue = [[y, x]] while queue: a, b = queue[0][0], queue[0][1] del queue[0] for i in range(4): ny = a+dx[i] nx = b+dy[i] if 0

티스토리툴바