bfs (4) 썸네일형 리스트형 [BOJ/파이썬] 골드2 1167 - 트리의 지름 💬 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 🔨 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다. 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진.. [프로그래머스/python] Level2 - 무인도 💬 문제 🔨 입출력 💡 해결 문제를 보고 기본적인 탐색 문제라서 다시 한번 되짚어 본다는 느낌으로 풀었다. 최단 거리를 묻지 않고 기본 탐색 이기 때문에 DFS를 한번 써볼려고 했다. map에 있는 자료들을 arr로 옮겨놓고 원래는 "X"로 되어 있는 공간을 arr에 0으로 채워주었다. 그런데 이걸 깜빡하고 나중에 조건에서 arr != "X"라고 하여 꽤 시간을 뺐겼다.. 뭐 이정도는 금방 풀었는데 중요한건 프로그래머스 환경에서 제출시 런타임 에러가 나는 것이었다. 내가 잘못 푼 줄 알고 코드를 고치다가 단톡방에 물어봤는데.. sys.setrecursionlimit을 사용하여 재귀횟수에 제한을 걸라는 것이었다. import sys sys.setrecursionlimit(int(1e7)) 이게 뭐람.. 백.. [JAVA11/알고리즘] 7-8 송아지 찾기 1 (BFS : 상태트리탐색) 💬 문제 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. 🔨 입력 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다. 출력 🔨출력 점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다. 👊🏻 예시 입력 1 5 14 👊🏻 예시 출력 1 3 💡 해결 제목부터 .. [JAVA] 이진트리에서 BFS 구현하기 BFS란? Bredath First Serach 한국말로 번역하면 너비 우선 탐색이다. 너비 우선 탐색은 저번 포스팅 했던 DFS와 마찬가지로 트리나 그래프를 방문 또는 탐색하는 방법이다. 탐색 방법은 다음과 같다. 1. 루트에서 시작하여 자식 노드들을 [1]에 저장한다. 2.[1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다. 3.[2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다. 4.위의 과정을 반복하여 모든 노드를 방문하면 탐색을 마친다. DFS와 BFS의 탐색 순서의 차이를 확연하게 알 수 있다. DFS와의 차이점 중 가장 큰 것은, 여러 갈래 중 경로의 길이가 무한하고 탐색 목표가 다른 경로에 존재하는 경우 DFS로 탐색할 시에는 무.. 이전 1 다음
