본문 바로가기

Graph3

[python] 7562번 - 나이트의 이동 문제 파이썬 풀이 나이트의 이동을 좌표로 나타내면 다음과 같다. 따라서 이동 좌표들을 위와 같이 설정한 후 이동 반복문을 8번 반복하여 이동을 해준다. 그리고 이동할 때마다 이전 값에 +1한 값을 저장해준다. 그리고 목적지 좌표가 나오면 그 값에서 -1한 값을 리턴해준다(1부터 시작했으므로) 이동 좌표를 빼고는 이전 bfs들과 동일하다. from collections import deque import sys input = sys.stdin.readline t = int(input().rstrip()) def bfs() : dx = [-1, 1, 2, 2, 1, -1, -2, -2] dy = [2, 2, 1, -1, -2, -2, -1, 1] q = deque() q.append((startX, star.. 2021. 12. 13.
[python] 1697번 - 숨바꼭질 문제 파이썬 풀이 이동을 1칸씩 하던 이전과 달리 한칸과 2배 이동하는 순간이동이 추가되었다. 그래서 이동 변수를 함수 안에서 설정하고 [x-1, x+1, 2 * x]로 설정하여서 해당 위치에서 탐색을 진행하도록 하였다. 그리고 이동할 때마다 저장된 값을 1씩 증가하여 시간을 기록했다. 그리고 x의 값이 k와 같으면 x에 기록된 값을 리턴하도록 하였다. 1부터 시작했기때문에 마지막 출력에서는 1을 뺀 값을 출력하도록 하였다. 그런데 처음 작성한 코드에서 시간 초과가 나왔다. 시간초과가 나온 코드 from collections import deque import sys input = sys.stdin.readline n, k = map(int, input().rstrip().split()) q = dequ.. 2021. 12. 13.
트리와 그래프 내용 정리 트리와 그래프 그래프란? 그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다. 그래프의 종류 무방향 그래프 간선에 방향이 존재하지 않아 양방향으로 이동이 가능하다. (A,B), (B,A)는 동일한 간선이다 방향 그래프 간선에 방향이 존재하는 그래프로 지정된 방향으로만 이동이 가능하다. A->B로 가는 간선은 로 표시하며 와는 다른 간선이다. 가중치 그래프 간선에 비용이나 가중치가 할당된 그래프이다. 완전 그래프 한 정점에서 모든 다른 정점과 연결되어 최대의 간선수를 가지는 그래프 단순 그래프 두 정점 사이의 연결선이 최대 한 개인 그래프 부분 그래프 원래의 그래프에서 일부 정점이나 간선을 제거해 만든 그래프 그래프 구현 방.. 2021. 12. 5.

티스토리툴바