분류 전체보기 (644) 썸네일형 리스트형 백준 : 2842 JAVA https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 문제 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다. 매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 www.acmicpc.net 집배원 한상덕 문제... 문제를 푸는데 사용한 알고리즘은 우체국에서 K를 갈수있는 가를 검증하기 위한 BFS 그리고 java의 Tr.. DFS를 Stack을 이용해서 풀어보자. https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 재귀함수를 이용하는게 아닌 Stack구조를 이용하여서 문제를 풀어보았다. 기존 DFS 탐색은 Stack 많은 값이 쌓이면 스택오버플로우를 일으킨다. 하지만 Stac.. 유니온 파인드 : JAVA 정의 어떤 그래프에서 서로 인접한 그래프가 있을때 특정 노드 u와 v가 서로 같은 그래프에 있는가를 판별할 때 사용하는 방법이다. graph[i][j] = 1 이라는 것은 서로 연결되어 있다는 뜻이다. 만약 서로 연결되어 있다면 Union 두개의 노드를 같은 집합으로 합친다는 뜻이다. 이때 Find(i) Find(x) 를 하게 되는데 Find는 가장 위에 있는 부모의 값을 리턴하고 재귀과정에서 연결되 Node를 부모 노드에 바로 붙여준다. 이렇게 되면 처음 parent값은 한다리를 거쳐간다는것인데 이렇게되면 parent[x]의 값은 x가속한 집합이라고는 할수 없다. 하지만 각각에대해 Find를 돌리면 find가 재귀적으로 가장 부모노드에 연결시켜주므로 값이 제대로 나오는 것을 확인 할 수 있다. 소스코드.. 정렬 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 package test; import java.util.Arrays; import java.util.Comparator; public class test { public static class Chemi implements Comparable{ int x; int y; public Chemi(int x, int y) { super(); this.x = x; this.y = y; } @Override public int compareTo(Chemi o) { // TODO Auto-gener.. 백준 : 11279 우선순위 힙을 사용해보자 자바의 PriortyQueue 라이브러리는 기본적으로 min힙으로 구성되어있다. 하지만 다음과 같은 방법으로 우선순위를 바꾸어서 쉽게 문제를 해결할수있다. 출력은 속도를 올리기위하여 Builder를 이용했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 package com.ssay.algo; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Collections; import java.util.PriorityQueue; pu.. 백준 : 16637 https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다. 수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9× www.acmicpc.net package com.ssay.algo; import java.io.BufferedReader; import java.io.IO.. 백준 : 17471 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net package com.ssay.algo; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class B17471 { public static int N; public static int population[]; public sta.. 백준 : 6593 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서 www.acmicpc.net 상범 빌딩 단순한 큐구현후 BFS를 구현하면된다. 3차원평면이기때문에 check[][][] 3차원으로 구현하면 중복을 방지할수가 있다... 이전 1 ··· 70 71 72 73 74 75 76 ··· 81 다음