백준 그래프 탐색

    [백준, BOJ 4963] 섬의 개수 (java)
    Problem Solving/BOJ

    [백준, BOJ 4963] 섬의 개수 (java)

    https://www.acmicpc.net/problem/4963메모리: 16,044 KB , 시간: 152 ms사용 알고리즘: 그래프 이론, 그래프 탐색, 너비 우선 탐색import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Queue;import java.util.StringTokenizer;public class Main { static int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1}; static int[] dy = {0, 0, -1, 1, -1, 1, -1, 1}; static int w, h; static int[]..

    [백준, BOJ 17142] 연구소 3 (java)
    Problem Solving/BOJ

    [백준, BOJ 17142] 연구소 3 (java)

    https://www.acmicpc.net/problem/17142메모리: 26,156 KB , 시간: 240 ms사용 알고리즘: 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 백트래킹바이러스가 어디에 존재하는지 ArrayList에 담아 따로 관리해 준다.각 바이러스마다 해당 바이러스만 활성화했을 때, 모든 곳에 바이러스를 확산시키기 위해 얼마만큼 시간이 걸릴지 spread_time 배열에 정보를 저장해 둔다.바이러스들 중 M개의 바이러스를 백트래킹을 통해 골라준 후, 고른 M개의 바이러스들을 활성화시켰을 때 최대 시간을 구해준다.M개의 바이러스 조합 중 최대 시간이 가장 짧은 시간을 답으로 출력한다. 이 문제를 해결하면서 한 가지 헷갈렸던 조건은 활성 바이러스가 비활성 바이러스가 ..

    [백준, BOJ 9466] 텀 프로젝트 (java)
    Problem Solving/BOJ

    [백준, BOJ 9466] 텀 프로젝트 (java)

    https://www.acmicpc.net/problem/9466메모리: 307,900 KB , 시간: 1,352 ms사용 알고리즘: 깊이 우선 탐색, 그래프 이론, 그래프 탐색import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int[] s; static boolean[] visited; static int[][] order; static int result; public static void main(String[] args) throws Exception{ BufferedReader br = n..

    [백준, BOJ 13905] 세부 (java)
    Problem Solving/BOJ

    [백준, BOJ 13905] 세부 (java)

    https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 메모리: 128,500 KB , 시간: 908 ms 사용 알고리즘: 데이크스트라, 그래프 탐색, 그래프 이론, 분리 집합, 자료 구조 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.PriorityQueue; ..

    [백준, BOJ 3055] 탈출 (java)
    Problem Solving/BOJ

    [백준, BOJ 3055] 탈출 (java)

    https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의..

    [백준, BOJ 2458] 키 순서 (java)
    Problem Solving/BOJ

    [백준, BOJ 2458] 키 순서 (java)

    https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 문제 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 1번 학생의 키 < 5번 학생의 키 3번 학생의 키 < 4번 학생의 키 5번 학생의 키 < 4번 학생의 키 4번 학생의 키 < 2번 학생의 키 ..

    [백준, BOJ 9205] 맥주 마시면서 걸어가기 (java)
    Problem Solving/BOJ

    [백준, BOJ 9205] 맥주 마시면서 걸어가기 (java)

    https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 문제 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다. 상근이의 집에서 페스티벌이 열리는..

    [백준, BOJ 1194] 달이 차오른다, 가자. (java)
    Problem Solving/BOJ

    [백준, BOJ 1194] 달이 차오른다, 가자. (java)

    https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제 지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다. 민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 ..

    [백준, BOJ 11725] 트리의 부모 찾기 (java)
    Problem Solving/BOJ

    [백준, BOJ 11725] 트리의 부모 찾기 (java)

    https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 예제 입력 1 7 1 6 6 3 3 5 4 1 2 4 4 7 예제 출력 1 4 6 1 3 1 4..

    [백준, BOJ 1600] 말이 되고픈 원숭이 (java)
    Problem Solving/BOJ

    [백준, BOJ 1600] 말이 되고픈 원숭이 (java)

    https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 ..

티스토리툴바