본문 바로가기

BFS4

99클럽 코테 스터디 12일차 TIL (7569번: 토마토) 문제https://www.acmicpc.net/problem/7569 학습 키워드BFS 시도(시간 초과) 완전 탐색day를 1부터 H*N*M 까지 탐색하면서 모든 배열을 순회하면서 토마토를 익히고, 익은 개수를 센다.첫 째날부터 익은 토마토가 없다면 0을 반환한다.익은 토마토가 없다면 날짜를 출력한다. 이때, 배열에 0이 포함되어 있다면 -1을 출력하고, 아니라면 날짜를 출력한다.(성공) 익은 토마토를 기준으로 BFS값을 입력 받을 때, Queue에 익은 토마토의 위치를 추가한다. 이때, 현재 토마토가 익은 날짜가 언제인지 알 수 있는 값도 같이 추가한다.BFS 방식으로 Queue의 맨 앞 값(poll)을 빼내주면서하면서 익은 토마토 주변('앞', '뒤', '상', '하', '좌', '우')에 있는 익지.. 2024. 11. 8.
99클럽 코테 스터디 10일차 TIL (18352번: 특정 거리의 도시 찾기) 문제https://www.acmicpc.net/problem/18352학습 키워드BFS 시도출발 도시부터 시작해서 연결되있는 가까운 도시를 탐색한다. 탐색하면서 이동한 거리를 저장하고, 만약 이동한 거리가 주어진 K와 같다면 정답에 추가한다. 풀이 및 코드List listAnswer : 거리 정보 K와 거리가 같은 도시의 목록Map> graph : 도시간 연결을 Map으로 표시했다. 예제 입력 1을 기준으로 1: {2, 3}, 2: {3, 4}와 같이 저장된다.boolean[] visited : 해당 도시를 이미 탐색했는지 판단하기 위한 배열int[] distance : 출발 도시 X부터의 거리를 저장하기 위한 배열 import java.util.*;import java.io.*;public class .. 2024. 11. 6.
99클럽 코테 스터디 8일차 TIL (2644번: 촌수계산) 문제https://www.acmicpc.net/problem/2644학습 키워드BFS 시도(성공) 촌수를 계산해야하는 두 번호(a, b)의 조상까지 탐색하면서 같은 조상이 있는 지점까지 탐색한다. 그 다음, 두 번호(a, b)에서부터 같은 조상의 위치까지 1씩 더해가면서 거리를 찾는다.(성공) a부터 시작해서 b까지 BFS를 통해 거리를 구한다.풀이 및 코드visited: 이미 탐색한 정점은 다시 탐색하지 않기 위해서 필요한 배열distance: a부터 시작해서 각 정점에 도달했을 때, 거리가 몇인지 저장하는 배열현재 정점에서 가까운 정점부터 시작해서 탐색하고, 각 정점에 도달할 때마다 거리를 저장한다. 만약 목적지에 도달했다면 해당 목적지의 거리를 반환하고, 목적지에 도달하지 못 했다면 -1을 반환한다.. 2024. 11. 4.
99클럽 코테 스터디 5일차 TIL (24444번: 알고리즘 수업 - 너비 우선 탐색 1) 문제https://www.acmicpc.net/problem/24444 학습 키워드BFS 시도BFS를 사용해서 풀면된다. 풀이무방향 그래프이므로 map에는 u와 v 양쪽 다 저장해야한다.put(u, v);put(v, u);각 정점이 출력된 순서를 저장하는 orders와 출력 순서를 기억하기 위한 orderIndex를 선언한다.탐색했는지 여부를 저장하기 위한 visited를 선언한다.BFS 방식으로 탐색하면서 각 정점이 추가되는 지점을 찾아 order에 기록한다.import java.util.*;public class Main { private static int N; private static int M; private static int R; private static Map> map; private .. 2024. 11. 1.

티스토리툴바