1. 문제 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net i번째 숫자가 j번째에 도달할 수 있는지 출력한다. 가능하면 1, 불가능하면 0을 출력 2. 어떻게 풀까? 입력으로 주어지는 형식이 인접행렬일 뿐 결국 간선의 정보이다. 그러므로 평소 풀던것 처럼 `ArrayList []`를 생성하여 간선의 정보를 저장한 뒤, 1부터 N번째 숫자를 차례로 BFS 탐색을 진행하기로 했다. 만약 1을 시작으로 BFS 함수를 호출하면 1에서 다른 요소인 {2,3,4,5,6} 에 도달할 수 있는 탐색을 통해 알아낸다. // 1부터 N까지 각 BFS 탐색 ..

1. 💎 문제 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 케빈 베이컨은 모든 사람과 케빈 베이컨 게임을 했을 때 나오는 단계의 합이다. 2. 🤔 어떻게 풀까? 사람마다 한명 씩 모든 사람과의 케빈 값을 구한 후 모두 더해, 가장 낮은 사람을 출력하면 되겠다. 케빈 값을 구하는 방법은 DFS를 사용해서 깊이를 더해주면서 구하면 되겠다. 하지만 틀렸다. DFS를 사용하면 모든 사람과의 관계의 단계를 알 수 있지만..

1. 💎 문제 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 2. 🤔 어떻게 풀까 이 문제는 점점 물들이는 문제로 익숙한 BFS문제로 느껴졌다. 그래서 BFS로 풀기로 하였고 출력 결과를 봤을 때 시작 점을 기준으로 거리가 늘어나는 것을 보아 시작점부터 탐색을 진행하며, depth을 관리하면서 풀면 되겠구나 생각했다. 3. 💡로직 1. 지도를 입력 및 시작점 받기 이중 for문으로 지도를 입력받는 형태에서 stream을 이용한 형태로 바꿨는데 시간이 훨씬 단축되는 ..

1. 📄 문제 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 2. 🤔 어떻게 접근할까 문제가 길어 차근 차근 그림으로 그리니 짝수와 홀수번으로 나누어졌다. 그래서 짝수와 홀수번 로직을 따로 구현한다로 생각했다. 또한 폭탄이 터지는 기준은 폭탄이 있는 위치에서 상하좌우 4개의 폭탄이 터져 없어지기 떄문에, 폭탄의 위치를 큐에 넣어 터질 시간이 되면 큐에서 꺼내어 상하좌우를 알아보기로 생각했다. 이 정도만 생각하고 바로 풀었는데 몇 몇 막히는 부분이 있었다. 3. 💡 생각해야 할 점 먼저, 폭탄은 설치 후 3초가 지나야 터진다는 ..

문제 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 어떻게 풀것인가? 트리 형태를 만든 다음 삭제 노드를 부모 노드와 끊어준다. 노드의 부모는 무조건 1개이기 때문에, 끊어주면 탐색을 할 수 없다. 트리를 DFS 탐색으로 탐색을 진행한다. BFS나 DFS 둘다 되겠지만 구현이 쉬운 BFS를 선택했다. 문제 알고리즘 parent 배열에 각 노드의 parent 값을 저장한다. parent 배열 이용하여 삭제할 노드를 부모 노드에서 제거 한다. BFS 탐색을 진행하면서 leaf 노드를 찾는다. 주의할 점 루..