취미처럼

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net import java.util.*; import java.io.*; public class Main { static int N, M; static int[][] map; static int[][] visit; static int[] dy = {0, 1, 0, -1}; static int[] dx = {1, 0, -1, 0}; static int min = Integer.MAX..

다익스트라(Dijkstra) 최단경로 알고리즘 그리디 알고리즘으로 분류 - 매번 가장 비용이 적은 노드를 선택해서 반복 DFS/BFS 의 경우 모든 노드간의 가중치가 같고, 얼마나 적은 수의 노드를 거쳤는지 탐색 다익스트라의 경우 노드간의 가중치가 달라서 얼마나 적은 가중치의 합으로 목적지에 도착했는지 탐색 출발 노드 설정 최단 거리 테이블 초기화 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 3번 4번 반복 시간복잡도 : O(N²) 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차탐색)한다. 우선순위 큐 우선순위가 가장 높은 데이터를..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net * 2 의 경우 이동 시간이 0초라서 증가하지 않으므로 다른 이동 보다 먼저 계산되어야 함 import java.util.*; import java.io.*; class Node { int x; int time; public Node(int x, int time){ this.x = x; this.time = time; } } public class Main { s..

https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 화면에있는이모티콘수, 클립보드에 있는 이모티콘수 를 이차원 배열로 상태관리 import java.util.*; import java.io.*; public class Main { static int max = 1001; static int S; static boolean[][] visit = new boolean[max][max]; public static void main(String[] args..

https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net parent 배열에 직전 번호를 기록하여 이동 경로 저장 import java.util.*; import java.io.*; public class Main { static int N; static int K; static boolean[] visit = new boolean[100001]; static int[] arr = new int[100001]; stat..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net N과 K가 같을 경우의 처리를 해줘야 한다. import java.util.*; import java.io.*; public class Main { static int N; static int K; static int[] visit = new int[100001]; public static void main(String[] args) throws Exception { S..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net import java.util.*; import java.io.*; class Node { int y; int x; Node(int y, int x) { this.y = y; this.x = x; } } public class Main { static int l; static int[][] map; static boolean[][] visit; static int[][] dr = { { -2, -1..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 익지 않은 토마토의 카운트를 세서 익었다는 처리를 할 때 빼줌 방문여부를 누적해서 최종 날짜를 셈 import java.util.*; import java.io.*; class Node { int y; int x; Node(int y, int x) { this.y = y; this.x = x; } } public class Main { // 가로 static int M; // 세로..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net import java.util.*; import java.io.*; class Node { int y; int x; Node(int y, int x) { this.y = y; this.x = x; } } public class Main { static int N; static int M; static int[][] map; static boolean[][] visit; static int[] dy = { 0, 1, 0, -1 }..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net import java.util.*; import java.io.*; public class Main { // 정사각형 크기 static int N; // 아파트 static int[][] map; // 방문여부 static boolean[][] visit; // 방향 static int[] dy = { 0, 1, 0, -1 }; static int[] dx = { 1, 0, -1, 0 }; // 단..