DFS

    [Java] 백준 1937 (욕심쟁이 판다) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1937 (욕심쟁이 판다) Gold 3

    Problem : https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net Approach 어느 한 지점으로부터 시작하여 최대 몇개의 지점을 방문할 수 있는지를 판단하는 DFS문제이다. DFS는 인접행렬의 경우 O(n^2)의 시간복잡도를 가지고 있어, n의 크기가 크다면 모든 지점을 시작지점으로 하여 DFS하기에는 시간초과가 뜰 것이다. (O(n^2 * n^2)) 따라서 위와 같이 시간초과를 피하기 위하여, 모든 점을 시작지점으로 DFS를 수행..

    [Java] 백준 1261 (알고스팟) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1261 (알고스팟) Gold 4

    Problem : https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net Approach 이 문제의 기본 접근법은 갈 수 있는 곳 중 벽이 아닌 곳이 있으면 우선 그 쪽으로 가고, 갈 수 있는 곳이 벽인 곳밖에 없다면 벽을 뚫는다.이다. 이를 구현하는 데에는 여러 방법이 있겠지만, 나는 Deque+BFS, PriorityQueue+BFS 두 가지 방법으로 풀이를 해봤다. 두 방법 모두 풀이가 가능하다. 주의할 점은, 큐에 동일한 ..

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

    [Java] 백준 1167 (트리의 지름) Gold 3

    Problem : https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net Approach BFS 나 DFS 를 사용하여 풀 수 있는 문제이다. 상식으로 접근하여 생각하면 쉽게 풀리는 문제였다. BFS나 DFS를 두번 수행하면 풀이가 가능한 문제이다. (나는 BFS를 사용했다.) 아무 정점을 시작으로 BFS를 수행하여 시작 정점으로부터 가장 먼 정점을 구한다. 그 정점을 기준으로 다시 BFS를 수행하여 가장 먼 정점까지의 거리가 트리의 ..

    [java] 프로그래머스 (여행경로) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (여행경로) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr Approach DFS 를 활용하여 풀이가 가능한 문제이다. 이름의 알파벳 순서가 앞서는 경우부터 방문해야 하므로 방문공항기준 오름차순으로 정렬하고 시작한다. 출발지는 항상 ICN 이므로 ICN을 출발지로 하여 DFS를 수행한다. 티켓을 모두 사용해야 하므로, 시작공항을 제외한 방문공항은 티켓의 개수와 같다.를 이용하여, 티켓을 처음 다 썼을 때의 경로를 ans에 담..

    [java] 프로그래머스 (타겟 넘버) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (타겟 넘버) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr Approach BFS나 DFS로 탐색하여 target number에 몇번 도착하는지를 계산하면 된다. 보통 DFS/BFS 는 목적지까지의 최소비용을 구하는데에 사용하지만, 이 문제에서는 최소비용이 아니라 몇번 도착하는지를 구하면 된다. Code public class TargetNumber..

    [java] 백준 2629 (양팔저울) Gold 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 2629 (양팔저울) Gold 2

    Problem : https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net Approach 주어진 추들의 무게로 구슬의 무게를 확인할 수 있는지를 판단하는 문제였다. 구슬을 목적지라고 가정한다면, 목적지를 갈 수 있는지를 판단하는 문제다. 따라서 필자는 깊이우선탐색을 이용하여 풀이를 하였다. 일단, 탐색 진행 방법에는 3가지 방법이 있다. 무게를 확인할 구슬은 항상 저울의 왼쪽에 놓는다고 가정하였을 때, 다음 구슬을 저울의 오른쪽에 올리는 경우(w + w..

    [java] 백준 2667 (단지번호붙이기) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 2667 (단지번호붙이기) Silver 1

    Problem : https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net Approach 보통 지도 형식의 배열이 나오면 BFS로 푸는게 더 나은 것 같다...(필자 생각) BFS, DFS 모두 풀이가 가능해도 더 좋은 풀이가 있는 문제처럼, 지도를 통한 탐색의 경우 필자는 BFS를 더 선호한다. (더 간단하기 때문 ㅎㅎ) 이 문제는 감을 익히기 위해서 두 방법 모두로 풀어봤다. 또한 이 문제는 프로그래머스에도 유사한 문제가 있다. 밑의 링크는 그 문제..

    [java] 백준 2606 (바이러스) Silver 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 2606 (바이러스) Silver 3

    Problem : https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net Approach 여러 노드가 있을 때, X 라는 노드와 연결된 모든 노드의 개수를 구하면 되는 문제이다. -> 따라서 순회 문제라는 것을 빠르게 알아내어, 접근해야한다. DFS, BFS 중 아무거나 사용해도 되지만, 필자는 인접리슽으를 이용한 DFS 재귀 방식으로 풀이하였다. Code import java.io.*; import java.util.*; /** * no.2606: 바이러..

    [java] 백준 1260 (DFS와 BFS) Silver 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 1260 (DFS와 BFS) Silver 2

    Problem : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net Approach BFS(Breadth-First Search), DFS(Depth-First Search) 의 기본 문제이다. 일단 BFS, DFS 가 어떤 방식으로 돌아가는지를 알아야 한다. 사전적 정의는 DFS는 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다는 방식이고..

    [java] 백준 14226 (이모티콘) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 14226 (이모티콘) Gold 5

    문제 원문 링크 : https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net Approach DFS 를 이용한 DP문제이다. 문제의 조건 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 이 문제를 풀려면 이모티콘의 길이가 X일 때, 현재 클립보드에 저장된 이모티콘의 길이가 몇인지를 저장해 놓아야 한다. 그래야 X보다 큰 길이Y의 이모티콘을 만들 때..

티스토리툴바