알고리즘/BFS 썸네일형 리스트형 백준 5567번: 결혼식 (JAVA) 문제 해석 친구의 친구까지만 결혼식에 초대할 수 있다. 결혼식에 초대 가능한 친구들은 총 몇명인지 출력한다. 상근이의 학번은 1이고 사람들은 각자의 학번을 가지고 있다. 알고리즘 친구 관계를 그래프로 구현하고 상근이를 기준으로 친구 또는 친구의 친구인 사람들은 상근이를 루트 노드로 생각했을 때 깊이가 1이거나 2인 사람들이다. 따라서 그래프 구현 후 BFS를 이용해 친구 관계를 탐색하는데 탐색 후 사람들의 깊이를 저장하고 깊이가 1 또는 2인 사람들의 수를 출력한다. 코드 더보기 백준 2644번: 촌수계산 (JAVA) 문제 해석 주어지는 두 사람 간의 촌수를 출력해야 한다. 둘 중 누구를 기준으로 촌수를 구하여도 같은 값이 나온다. 알고리즘 사람들간의 관계를 그래프로 구현하고 두 사람 중 한 사람으로부터 나머지 한 사람을 탐색하기까지의 깊이를 출력한다. 여기서는 BFS를 통해 탐색하였다. 깊이도 구해야하기 때문에 메모리 낭비를 줄이기 위해 방문 여부를 깊이 값으로 확인할 수 있도록 구현하였다. 두 사람의 관계가 이어져있다면 result에 원하는 결과값이 저장되도록 하고 아니면 그대로 -1을 출력한다. 코드 더보기 백준 11724번: 연결 요소의 개수 (JAVA) 문제 해석 무방향 그래프가 주어지고 해당 그래프의 연결 요소 개수를 구해야 한다. 알고리즘 그래프를 인접 행렬, 리스트 등을 이용하여 구현하고 탐색을 통해 연결 요소의 개수를 구한다. 연결 요소의 개수는 그래프 내의 하위 그래프의 수이다. 여기서는 리스트를 이용해 그래프를 구현하고 BFS로 탐색하였다. 코드 더보기 백준 11725번: 트리의 부모 찾기 (JAVA) 문제 해석 주어진 트리에서 각 노드의 부모 노드를 찾아라. 알고리즘 그래프를 이용하여 트리를 구현하고 BFS를 통해 부모 노드를 탐색한다. 코드 더보기 백준 18352번: 특정 거리의 도시 찾기 (JAVA) <BFS> 문제 해석 단방향 그래프가 주어진다. 출발지를 입력값으로 지정해주고 출발지에서 시작해 최단거리 K를 만족하는 모든 도시를 출력해야 한다. 알고리즘 처음에는 모든 가능한 경우를 모두 탐색해야 한다 생각하여 인접행렬을 이용해 DFS를 구현하였다. 하지만 그 결과 메모리 초과 오류가 발생하였다. 인접행렬로 구현하여 불필요한 메모리까지 모두 사용한다 생각하여 연결 리스트를 활용해 DFS를 재구현하였다. 연결 리스트를 활용해 불필요한 메모리 사용을 줄였지만 그럼에도 메모리 초과가 발생하였다. 또 어느 부분에서 메모리를 줄일 수 있을까 생각을 해보았다. 메모리를 줄일 수 있는 부분은 이제 방문 기록을 체크하기 위해 사용한 visited와 최단거리를 저장하기 위한 result이다. 그런데 기본적으로 최단거리 문제를 .. 더보기 백준 9372번: 상근이의 여행 (JAVA) <BFS> 문제 해석 테스트 케이스 T가 주어진다. 테스트 케이스 실행시 처음에 국가의 수 N과 비행기 종류 M이 주어진다. 비행기 종류 M만큼 각 비행기가 운행하는 국가들이 주어진다. ex) 1 2가 주어질시 1국가와 2국가 운행(왕복) 모든 국가를 여행해야하고 타는 비행기 종류를 최소한으로 해야한다. 알고리즘 사실 이 문제는 풀 의미가 없었다. 모든 국가를 무조건 여행해야 하는 상태에서 비행기 종류 하나당 운행편이 한개뿐이고 같은 경로를 가진 두 개의 비행기가 있더라도 비행기 종류를 최소화해야 하고 경유해서 가는 경우를 허용하면서 비행기 타는 횟수는 고려하지 않기에 정답은 어떤 입력이 들어오든 무조건 N-1이다. 하지만 원래 BFS로 푸는 문제이고 BFS 연습을 하고자 인접행렬을 이용하여 노드 간 관계를 나타내.. 더보기 이전 1 다음
