PS
-
[백준 1389번] 케빈 베이컨의 6단계 법칙-JAVAPS 2023. 10. 5. 14:55
문제 링크 문제 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까? 천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다...
-
[백준 21736번] 헌내기는 친구가 필요해 - JAVAPS 2023. 10. 3. 23:44
문제 링크 너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색을 통해 풀이할 수 있는 문제이다. 접근 방법 문제 설명에 나와있듯 주어진 위치에서 위, 아래, 좌, 우로 배열을 탐색해 타겟 찾고, 그 수만큼 카운트한다. 조건 벽(‘X’)으로 둘러 쌓인 곳은 접근할 수 없고, 배열의 크기를 벗어난 범위 역시 마찬가지이다. 타겟(‘P’)를 발견하더라도 더 탐색할 수 있다면 종료하지 않고 계속해서 탐색한다. 만약 탐색이 종료되었고, 타겟을 찾은 개 수가 0이라면 'TT’를 출력한다. DFS 혹은 BFS는 기본적으로 배열을 탐색할 때 무한 루프에 빠지지 않기 위해 방문 여부를 확인해야 할 필요가 있다. 추가로 이번 문제에선 시작 지점이 주어져 있으므로 탐색 배열을 채워 나갈 때 해당 위치를 미리 저장하..