본문 바로가기

Java/백준

 (106)
[JAVA] 백준 1753 최단 경로 1753번: 최단경로 (acmicpc.net) 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net - 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오, - 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 - 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. - 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K가 주어진다. - 셋째 줄부터 E개의 줄에 걸쳐 각 간선..
[JAVA] 백준 1697 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net - 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0
[JAVA] 백준 2178 미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net - N*M 크기의 배열로 표현되는 미로가 있다. - 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. - 이러한 미로가 주어졌을 때, (1,1)에서 출발하여 (N,M)의 위치로 이동할 떄 지나야 하는 최소의 칸 수를 구하는 프로그램을작성하시오. - 한 칸에서 다른 칸으로 이동할 떄, 서로 인접한 칸으로만 이동할 수 있다, - 위의 예에서는 15칸을 지나야 (N,M)의 위치로 이동할 수 있다. 칸..
[JAVA] 백준 2667 단지번호붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net - 아래 그림과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. - 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. - 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. - 대각선상에 집이 있는 경우는 연결된 것이 아니다. - 는 을 단지별로 번호를 붙인 것이다. - 지도를 ..
[JAVA] 백준 24445 알고리즘 수업 - 너비 우선 탐색 2 24445번: 알고리즘 수업 - 너비 우선 탐색 2 (acmicpc.net) 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net - N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. - 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자 -너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 내림차..
[JAVA] 백준 24444 알고리즘 수업 - 너비 우선 탐색 1 24444번: 알고리즘 수업 - 너비 우선 탐색 1 (acmicpc.net) 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net - N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected grph)가 주어진다. - 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자. - 너비 우선 탐색 의사코드는 다음과 같다. 인접 정점으로 오름..
[JAVA] 백준 11049 행렬 곱셈 순서 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net - 크기가 N*M인 행렬 A와 M*K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N*M*K번이다. - 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다. - 예를 들어, A의 크기가 5*3이고, B의 크기가 3*2, C의 크기가 2*6인 경우의 행렬의 곱 ABC를 구하는 경우를 생각해보자. 1) AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 ..
[JAVA] 백준 11066 파일 합치기 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net - 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. - 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 하나의 임시파일을 만들고, 이 임시..

티스토리툴바