DFS

    [Java] 백준 16957 (체스판 위의 공) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16957 (체스판 위의 공) Gold 4

    Problem : https://www.acmicpc.net/problem/16957 16957번: 체스판 위의 공 크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다. 체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙 www.acmicpc.net Approach Union-Find 성격의 개념과 DFS를 혼용하여 풀이한 문제이다. 처음엔 모든 위치를 기준으로 DFS를 수행하여 정답을 구하였다. 이 방법은 TLE(Time Limit Error)가 발생한다. 그러므로 다른 방법을 사용해야 한다. 시간초과를 받은 코드와 정답처리를 받은 코드를 함께 게시하겠다. DFS는 불가피하다. 그러므로 DFS의 횟수를 줄이면서 알고..

    [Java] 백준 12886 (돌 그룹) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 12886 (돌 그룹) Gold 5

    Problem : https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 www.acmicpc.net Approach DFS를 사용하여 풀이한 문제이다. BFS로도 풀이가 가능한 것 같다. 새로 만든 숫자와 기존 숫자를 이용하여야 하기 때문에 DFS가 먼저 생각이나서 DFS로 풀이하였다. 먼저 처리할 수 있는 예외를 보자. (a + b + c) % 3이 0이 아니라면 세 숫자를 어떻게 선택하더라도, 서로 같게 만들 수 없다. 문제 풀이 로직은 다음과 같다. 숫자 a, b, c..

    [Java] 백준 16964 (DFS 스페셜 저지) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16964 (DFS 스페셜 저지) Gold 5

    Problem : https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net Approach 그래프 정보와 DFS 방문 순서가 주어졌을 때, 주어진 방문 순서가 유효한지를 판단하는 문제이다. 현재 노드 기준으로, 방문하지 않은 인접한 노드들을 모두 set에 넣는다. 그리고 다음 방문 순서가 올바른 DFS 순서인지를 판단한다. 주어진 방문 순서의 끝까지 검사하며, 다음 방문 순서가 set에 없다면 올바르지 않은 방문 순서..

    [Java] 벡준 16947 (서울 지하철 2호선) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 벡준 16947 (서울 지하철 2호선) Gold 3

    Problem : https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net Approach 그래프 정보가 주어졌을 때, 사이클을 구하고, 그 사이클로부터 얼마나 멀리 떨어져 있는지를 구하는 문제였다. 먼저 주의할 점은, 노드의 개수가 N개이고, 간선의 개수도 N개이므로, 사이클(순환선)은 무조건 1개 존재한다는 것이다. 문제 풀이의 순서는 다음과 같다. 먼저 사이클 찾은 뒤, 사이클에 속하는 노드들을 표시한다. (cycle 배..

    [Java] 벡준 16929 (Two Dots) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 벡준 16929 (Two Dots) Gold 4

    Problem : https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net Approach 행렬 정보가 주어졌을 때, 사이클이 존재하는지를 판단하는 문제였다. 사이클을 판별하는 방법은 여러가지가 있지만, 여기서는 DFS를 이용하였다. 모든 정점을 방문할 수 있도록, 방문하지 않은 모든 곳에서 DFS를 수행한다. 그 중에 사이클이 있다면, 더이상 진행할 필요가 없으므로 종료시켰다. 사이클을 판별하는 로직은 다음과 같다. 임의의 시작점에서 DFS를..

    [Java] 벡준 13023 (ABCDE) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 벡준 13023 (ABCDE) Gold 5

    Problem : https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net Approach DFS를 활용한 문제이다. 문제에서 요구하는게 이해가 어려울 수 있으나, 쉽게 얘기하자면 어느 하나의 노드에서 시작하여 깊이가 5이상인 그래프가 존재하는지를 판단하면 된다. 그래프의 최대 지름이 5 이상이면 1을 아니라면 0을 출력하면 된다. 그래프의 최대지름을 구하는 법은 다음과 같다. 임의의 노드에서 가장 먼(깊이가 가장 깊은) 노드를 찾는다. (DFS 로) 그 노드에서부터 다시 DFS를 진행하여 가장 먼 노드와의 길이를 측정한다. 두번의 DFS가 이루어져야 한다...

    [Java] 백준 17136 (색종이 붙이기) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 17136 (색종이 붙이기) Gold 2

    Problem : https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net Approach BruteForce + DFS + Backtracking 문제이다. DP로도 풀 수 있을까 고민했지만, 색종이의 개수 제한도 있고 개수를 어떻게 세야할 지 감이 안와서 다른 방법을 생각했다. 색종이를 붙일 수 있는 모든 곳에 대해서 색종이 사이즈가 5, 4, 3, 2, 1인 색종이를 붙일 수 있는지 각각 검사한다. 현재 사용한 색종이의 개수가 최솟값보다 ..

    [Java] 백준 16637 (괄호 추가하기) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16637 (괄호 추가하기) Gold 3

    Problem : https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net Approach 입력값이 크지 않아, DFS + BruteForce로 풀이가 가능한 문제이다. 중첩된 괄호는 허용하지 않으므로, 주어진 식의 앞에서부터 괄호를 씌운 경우와 씌우지 않은 경우 두가지 경우를 모두 고려한다. 그렇게 가지를 치며 모든 경우를 조사한다.(BruteForce) 그중 가장 큰 결과값을 내는 값들을 ans에 갱신한다. Code import ja..

    [Java] 백준 1987 (알파벳) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1987 (알파벳) Gold 4

    Problem : https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net Approach 이미 지나온 알파벳은 지날 수 없는 DFS 문제이다. 이미 지나온 알파벳은 지날 수 없다는 것을 확인하기 위해 visited 배열과 더불어 alpha 배열을 따로 두었다. 풀이 방법은 다음과 같다. 좌측 상단(0, 0)에서 시작하여 DFS를 수행한다. DFS 를 수행하며 지나온 알파벳을 기록한다. 이미 지나온 알파벳이라면 그 칸으로는 더이상 탐색하지 않는다..

    [Java] 백준 1967 (트리의 지름) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1967 (트리의 지름) Gold 4

    Problem : https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net Approach 트리를 가장한 DFS/BFS문제이다. 트리의 지름은 가장 먼 두 노드 사이의 길이를 구하면 된다. 가장 먼 두 노드 사이의 길이는 다음과 같이 구할 수 있다. 임의의 점에서 가장 먼 노드 A를 구한다. A에서 가장 먼 노드 B를 구한다. A - B 사이의 길이가 가장 먼 두 노드 사이의 길이가 된다. 머릿속에서나 잠깐 생각해보면 쉽게 이해가 갈..

티스토리툴바