https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 두가지 방법으로 해결하였다. Union Find 사용 Union 함수와 Find 함수를 만들어서 이어지는 지역끼리 부모가 같도록 만들어주었다. 여행 계획에서 부모가 다른 지역이 나타나면 NO를 출력한다. ArrayList 사용 ArrayList에 연결된 지역을 각각 담아주었다. 여행 계획에 나타나는 지역마다 BFS를 이용해 연결되는지 확인하고 그렇지 않다면 NO를 출력한다. 메모리와 시간 모..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net ** 1697번 숨바꼭질에서 이어짐 ** 풀이 기존 숨바꼭질과 동일하게 BFS를 이용하여 동생을 찾는다. 하지만 동생을 찾을 경우 카운트만 증가시키고 종료하지 않는다. 또한 이미 방문한 점이어도 최단 소요 시간보다 오래 걸리지 않는다면 다시 방문할 수 있다. 코드 import java.io.BufferedReader; import java.io.IOExcept..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 기준점에서 +1, -1, *2 된 점까지 가는 시간은 1초이다. 그래프의 인접 노드라고 생각할 수 있는 것이다. 따라서 BFS를 이용하여 1초 걸리는 지점을 방문 → 또 그 지점을 기준으로 1초 걸리는 지점을 방문을 반복하다 보면 각 점까지 도달하는 최소 시간을 찾아낼 수 있다. 동생의 위치인 K에 도달하면 반복을 멈추고 걸린 시간을 출력한다. 코드 import j..

https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 처음에는 문제가 잘 이해되지 않았지만, 결론적으로 이 문제는 연속으로 이어진 5개의 노드가 있는지 확인하는 문제이다. 따라서, DFS를 이용해 연결된 5개의 노드가 있는지 확인하면 된다. for 문을 이용해 0~N-1번을 각각 시작점으로 둔다. 그리고 인접한 노드를 찾은 뒤, 방문하지 않았다면 다시 인접 노드를 탐색한다. 이렇게 쭉 들어가다가 5번째 노드를 찾으면 종료하고, 찾지 못 했다면 이전의 노드로 돌아온다. 이 때, 이전 노드로 돌아왔다면 방금 찾았던 노드는 방문 체크를 해제해줘야 한다. ..