[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를 수행하여 가장 먼 정점까지의 거리가 트리의 ..

→2021.03.29

Algorithm/Programmers

[java] 프로그래머스 (가장 먼 노드) Level 3

Problem : https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr Approach 주어진 그래프의 1번 노드에서 가장 먼 노드의 개수가 몇개인지를 찾는 문제이다. DFS로 풀면 같은 그래프라도 답이 달라질 수 있다. (정확한 것은 아니고 예상(?)) 예를 들어, (1, 2), (1, 3), (2, 3) 라면, DFS는 1 -> 2 -> 3 순으로 진행되어 노드 3이 노드 1로부터 2거리에 위치한다고 판단한다. 그러나 BFS는 1 -> 2, 1 -> 3 순으로 진행하여 노드 3이 ..

→2021.01.30

Algorithm/Baekjoon Online Judge

[java] 백준 17472 (다리 만들기 2) Gold 3

Problem : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net Approach 삼성 A형 기출문제라고 한다. 만만치 않았다. 푸는 도중에도 풀이가 길어져서 이렇게 풀어도 되는지에 대해 계속 생각하게 만들었다. 문제 풀이에 앞서 크게 3가지의 알고리즘이 사용된다. 주어진 섬들의 numbering -> BFS/DFS numbering된 섬들끼리의 거리 계산 -> BruteForce(행렬로 주어졌으므로 다른 방법은 제한적이다..

→2021.01.30

Algorithm/Programmers

[java] 프로그래머스 (단어 변환) Level 3

Problem : https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr Approach 문자열을 이용한 BFS/DFS 문제이다. 보통의 DFS/BFS 는 연결된 간선을 이용해 탐색을 수행하지만, 이 문제에서는 서로 다른 글자가 단 한글자일 경우에만 탐색이 수행되므로, 서로 문자가 몇개 다른지를 검사해주어야 한다. 처음엔 HashMap을 사용해야 하나 싶었지만 주어진 파라미..

→2021.01.29

Algorithm/Baekjoon Online Judge

[java] 백준 4803 (트리) Gold 4

Problem : https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net Approach 트리의 기본성질을 이용한 문제이다. 트리의 경우 노드개수는 (간선의 개수 + 1)이다. 문제에서 각 테스트케이스마다 노드의 개수 n과 간선의 개수m이 주어진다. 노드가 연결되지 않은 경우도 있기 때문에, 모든 노드를 방문해 보아야한다. 또한, 양방향 간선으로 구성했기 때문에 주어진 그래프가 트리를 이룬다면 (간선의 개수 / 2 + 1)이 노드의 ..

→2021.01.28

Algorithm/Programmers

[java] 프로그래머스 (네트워크) Level 3

Problem : https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr Approach 간단하게 BFS/DFS 를 활용하여 풀 수 있는 문제이다. 나는 BFS 를 사용하였다. 모든 노드에 대하여 BFS 를 수행한 후, 집합의 개수가 몇개인지를 판별해주면 된다. Code import org.junit.jupiter.api.Assertions; import org.junit.jupiter.api.Test; imp..

→2021.01.27

Algorithm/Baekjoon Online Judge

[java] 백준 1707 (이분 그래프) Gold 4

Problem : https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net Approach 풀이에 시작하기 앞서 주의할 점을 소개한다. 이 문제는 은근히 반례를 찾는 유저들이 많았는데 대부분 다음과 같은 이유로 오답이 생겼을 것이다. 질문 게시판에 있는 djm03178님의 게시글을 인용하겠다. 테스트 케이스마다 초기화를 해야 한다. 똑같은 입력을 주었을 때 다른 출력을 내놓는다면 초기화가 되지 않은 상태일 것이다. 1번 정점에서만 탐색을 하..

→2021.01.07

Algorithm/Baekjoon Online Judge

[java] 백준 10217 (KCM Travel) Gold 1

Problem : https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net Approach 이 문제는 다익스트라 알고리즘과 DP를 같이 사용해서 풀어야했다. 인접리스트를 이용하여 그래프를 구성하였으며, 시간순 오름차순(시간이 같으면 비용순 오름차순)으로 구성하였다. 그런 후, 시작점 1부터 다익스트라 알고리즘을(BFS: PriorityQueue 이용) 적용하여, 비용을 초과하지 않는 선에서 모두 갱신해주었다. 다익스..

→2021.01.04

Algorithm/Baekjoon Online Judge

[java] 백준 2206 (벽 부수고 이동하기) Gold 4

Problem : https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net Approach 조건이 달려있는 경로 최소비용 문제이다. 필자는 BFS를 사용했다. 경우의 수를 따지기 전에, 현재 위치에서 벽을 부시고 왔는지에 대한 brokenWall[x][y] 배열이 필요하다. brokenWall[x][y] 의 값이 2이면, 해당 (x, y)를 아직 방문하지 않았다는 뜻이고, 1이라면, 해당 (x, y)를 방문했는데 방문하기전에 경..

→2020.12.30

Algorithm/Baekjoon Online Judge

[java] 백준 7569 (토마토2) Silver 1

Problem : https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net Approach 백준 7576번 토마토 문제와 같은 문제이지만, 3차원 배열로 구성된 문제이다. 7576번 문제의 풀이는 밑의 링크에 있다. 2020/12/30 - [Algorithm/Baekjoon Online Judge] - [java] 백준 7576 (토마토1) Silver 1 [java] 백준 7576 (토마토1) Silver 1 Problem : ..

→2020.12.30

티스토리툴바