본문 바로가기

백준 온라인 저지9

[python] 11725번 - 트리의 부모 찾기 문제 파이썬 풀이 트리를 그래프를 저장하듯 리스트 형태로 저장하고, 부모 노드를 저장하는 리스트를 생성하는 것이 포인트였다. 부모 노드를 저장하는 리스트는 리스트의 인덱스가 해당 노드가 되고 저장된 값은 부모 노드가 된다. 예를 들어보면 2와 연결되어있는 노드 들은 2의 부모 노드와 자식 노드로 나뉜다. 이때 부모 노드를 저장하는 리스트에서 2의 부모 노드가 무엇인지 가져와 2와 인접한 노드들 중 부모 노드를 제외한다. 그럼 나머지는 전부 2의 자식노드가 된다. 이제 자식 노드로 구별된 노드들의 부모 노드를 2로 저장한다. 이와 같은 과정을 모든 노드들에 접근하면서 부모 노드를 저장한다. 모든 노드들을 접근하는 과정에서는 dfs나 bfs를 이용하여 전체 탐색한다. 나는 dfs를 통해 구현하였다. from.. 2021. 12. 20.
[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.
[python] 7576번 - 토마토 문제 파이썬 풀이 최소 날짜를 구하기 위해서 BFS를 사용하고, 탐색을 할 때마다 이전 탐색 지점 + 1을 값으로 저장해주어 날짜를 저장해준다. 즉 마지막에 탐색하는 칸에는 가장 큰 값이 들어 있고, 1부터 시작했기 때문에 max값 -1 이 모두 익은 날짜 이다. 탐색을 어떤 식으로 시작을 해야할지에 고민이 많았는데 이 문제에서의 포인트는 미리 모든 토마토를 탐색하여 이미 익어있는 토마토를 탐색 큐에 집어넣고 탐색을 시작하는 것이 포인트였다. BFS 코드 def bfs() : while q : x, y = q.popleft() for i in range(4) : nx = x + dx[i] ny = y + dy[i] if nx = n or ny = m : contin.. 2021. 12. 12.

티스토리툴바