본문 바로가기

백준98

백준 2644번 : 촌수계산 문제 www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 구현 방법 인접리스트 생성해서 dfs로 구현하였습니다. 찾아야할 값 둘 중 하나는 찾으러 갈 타켓, 하나는 찾을 값으로 지정한 후 깊이로 +1 씩 카운팅을 해주었습니다. ans를 -1로 초기화하고 해당 값을 찾으면 카운팅 값 저장 후 return, 못 찾으면 ans를 그대로 출력해주었습니다. 구현 코드 package BOJ.silver; import java.io.BufferedReader;.. 2021. 3. 10.
백준 3184번 : 양 문제 www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 구현 방법 bfs로 구현하였습니다. 입력을 완료한 후 울타리 공간이 1, 그 공간에 늑대나 양이 있을 수 있으므로 '#'가 아닐 때만 탐색하게 해주었습니다. 탐색을 하면서 '#'가 아닐 때 이동을 해주고 이동한 곳이 양이나 늑대이면 각자의 카운팅을 올려주었습니다. 울타리 내 한 공간의 탐색이 끝난 후 늑대 카운트와 양 카운트를 비교한 후 늑대의 수가 양보다 크면 늑대의 값을 추가, 양이 더 크.. 2021. 3. 9.
백준 5567번 : 결혼식 문제 www.acmicpc.net/problem/5567 5567번: 결혼식 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다. www.acmicpc.net 구현 방법 bfs를 사용하여 구현하였습니다. 인접리스트를 생성하여 친구관계를 만들어주고 결혼식에는 친구와 친구의 친구까지 올 수 있으므로 카운팅 값을 넣어주었습니다. 상근이는 학번이 1이기 때문에 1부터 시작하여 상근이의 카운트는 0, 상근이에서 퍼져가는 친구는 상근이 카운트+1 해서 1, 친구의 친구는 친구 카운트+1 해서 2로 만들어 주고 현재 카운트+1이 3보다 크면 bfs에 못넣게 조건을 넣어주었습.. 2021. 3. 9.
백준 17086번 : 아기 상어2 문제 www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 구현 방법 처음에는 브루트포스로 구할 수 있는 전부를 구했습니다. 각자의 위치에서 bfs를 통해 제일 가까운 상어까지의 거리를 저장 후 최댓값을 구해주었습니다. 채점 후 시간차가 많이 나는 코드를 참고해보니 다른 생각으로 접근할 수 있다는 걸 깨달았고 참고해서 다시 짜보았습니다. 빈 칸이 중점이 아닌 상어를 중점으로 하여 입력되는 상어를 전부 queue에 넣어준 후 bfs를 통.. 2021. 3. 9.

티스토리툴바