dfs29

• 

  [백준/BOJ] 1937번: 욕심쟁이 판다 문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 처음에 문제를 봤을 때 "아 가장 길이가 짧은 곳에서부터 시작하면 되겠구나" 라는 생각을 하였다. 하지만 예시를 보고서는 "어라? 이게 왜 이 값이 나오지?" 하고 보니 꼭 최소 길이부터 시작한다고 가장 많이 간다는 것이 아니었다. 쨌든 이 문제를 dfs를 통해 푼다는 것은 변하지 않는다. 여기에 더해 dp를 추가로 이용했는데, 모든 칸을 dfs로 돌리면 시간이 오래 걸려 시.. PS(Problem Solving)/BOJ 2023. 1. 11.

• 

  [백준/BOJ] 9466번: 텀 프로젝트 문제 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 해설 우선 배열의 인덱스는 0부터 시작이므로 각 학생을 0번부터 시작하도록 -1을 해준다. 예시 입력1의 첫번째 테스트 케이스는 다음과 같이 된다. 학생들은 서로 원하는 경우에만 팀이 될 수 있다. 즉, 사이클이 형성되야만 팀이 될 수 있다는 것이다. 우선 필요한 변수들을 생각해보자. 이미 방문했던 칸은 재방문할 필요가 없으므로 방문 여부를 처리해줄 visited 배열을 선언한다. 또한 사이클이 .. PS(Problem Solving)/BOJ 2023. 1. 10.

• 

  [백준/BOJ] 10451번: 순열 사이클 문제 https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 해설 위 그림은 예제 입력의 첫 번째 테스트케이스이다. 색을 맞춰보면 case1. case2. case3 1 → 3 2 → 2 4 → 8 3 → 7 8 → 6 7 → 5 6 → 4 5 → 1 이처럼 3가지의 순환 사이클로 나뉘는 것을 확인할 수 있다. 이를 구현하는 방법을 알아보자. 나의 경우 Map에 인덱스와 값을 저.. PS(Problem Solving)/BOJ 2023. 1. 9.

• 

  [백준/BOJ] 14503번: 로봇 청소기 문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 해설 처음 문제를 해결하려 할 때 방향에 대해서 헷갈렸지만 별거 없는 것이었다. "바라보고 있는 방향의 왼쪽에 청소하지 않은 칸이 있다면 그 칸으로 이동한다". 즉, 내가 북쪽을 보고 있을 때, 서쪽을 보고 청소가 되있지 않다면 청소하러 가라인 것이다. 다음으로 4칸이 모두 벽과 청소한 구역으로 이루어져 있어 이동할 수 없는 경우 방향을 유지한 채로 뒤로 한칸 간다. 이때 뒤의 방향이 벽이.. PS(Problem Solving)/BOJ 2023. 1. 4.

• 

  [백준/BOJ] 1325번: 효율적인 해킹 문제 https://www.acmicpc.net/problem/1325 graph[a].add(b) 이 과정이 끝났다면 각 컴퓨터마다 dfs 알고리즘을 수행시켜 해킹할 수 있는 컴퓨터의 수를 세면 된다. dfs의 동작 방식은 코드를 보자. 코드 private lateinit var graph: Array private lateinit var visited: BooleanArray private lateinit var hacking: IntArray private var max = 0 fun main() = with(System.`in`.bufferedReader()){ val (computerCnt, trustCnt) = readLine().split(" ").map { it.toInt() } graph.. PS(Problem Solving)/BOJ 2022. 9. 23.

• 

  [백준/BOJ] 2644번: 촌수계산 문제 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 해설 부모자식 관계가 성립하는지를 저장하기 위해 ArrayList라는 자료형을 가진 graph를 선언하였다. 부모자식을 양방향으로 모두 저장하였다면 dfs를 통해 찾고자 하는 두 사람의 관계가 나올 때까지 dfs 알고리즘을 수행하면 된다. 코드 private lateinit var visited: BooleanArray private val graph = ArrayList.. PS(Problem Solving)/BOJ 2022. 9. 20.

• 

  [백준/BOJ] 1967번: 트리의 지름 문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 해설 한 정점에서 가장 멀리 있는 정점은 원의 지름 즉, 테두리에 해당되는 정점이다. 따라서 한 정점에서 가장 멀리 있는 정점을 구한 후, 그 정점에서 가장 멀리 있는 정점까지의 길이가 곧 원의 지름이 된다. 우선 가장 멀리 있는 한개의 정점을 구해야 한다. 이때 어떠한 정점에서 출발을 하든지 간에 가장 멀리 있는 정점은 지름에 해당하는 정점 중 하나이다. 지름에 해당하는.. PS(Problem Solving)/BOJ 2022. 8. 20.

• 

  [백준/BOJ] 1520번: 내리막 길 문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 해설 DFS로만으로 풀려다가 도저히 풀리지 않아 다른 분들이 써놓은 풀이를 참고하였다. DFS만을 이용하면 시간초과가 나게 되어 DP를 함께 사용하는 방법을 알 수 있었다. 각 현재 지점에서 4방향으로 탐색을 한다. 이 때 갈 수 있는 경우의 수를 저장하면서, DFS를 수행하게 된다. 만약 이미 탐색했던 지점이라면, 그 지점에서 갈 수 있는 경로의 수를 반환해준다. 도착 지점에 도착하게 되면 1을.. PS(Problem Solving)/BOJ 2022. 8. 8.

• [백준/BOJ] 15686번: 치킨 배달 문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 해설 브루트 포스(Brute Force) 문제이다. 문제에서 원하는 것은 결국, 모든 집에 대해 가장 가까운 치킨집까지의 거리의 합이다. 내가 푼 문제 해결 과정(알고리즘)은 다음과 같다. 맵을 입력받으면서, 집과 치킨집의 좌표를 저장해둔다. 모두 저장했다면, dfs를 수행하며 남길 치킨집을 선택한다. visited 배열을 방문처리를 해준 후의 갯수를 세고, 이를 다시 .. PS(Problem Solving)/BOJ 2022. 8. 2.

• [백준/BOJ] 11725번: 트리의 부모 찾기 문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 해설 DFS를 이용하여 해결할 수 있는 문제이다. 트리 상에 연결되는 두 정점이 부모-노드 구분이 없기 때문에 양방향으로 넣어줘야한다. 또한 문제에서 트리의 루트를 1이라고 정했기 때문에, 1은 먼저 방문처리 해준 후, DFS를 실행시킨다. 소스 코드 private lateinit var arr: Array private lateinit var parent: IntArray private lateinit var visited: BooleanArray fu.. PS(Problem Solving)/BOJ 2022. 7. 23.

• [백준/BOJ] 1245번: 농장 관리 문제 https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 해설 농장의 산봉우리를 찾아야 한다. 따라서 전체 탐색을 해줘야 한다. 8방향을 확인하며 자신보다 높은 곳이 있다면 temp를 false로 바꿔준다. 또한 한 지점을 방문할 때마다 방문여부처리를 체크해준다. 자신보다 높은 곳이 없다면, 그 위치가 산봉우리가 된다. temp가 true라면 봉우리의 갯수를 증가시킨다. 소스 코드 import java.util.* p.. PS(Problem Solving)/BOJ 2022. 7. 18.

• [백준/BOJ] 14502번: 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하.. PS(Problem Solving)/BOJ 2022. 7. 13.