https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 주의점! 벽부수고 이동하기1 과 달리 visited를 3중배열로 생성해야한다. 그 이유는 각 방문마다 벽을 1개 부시고 왔는지 2개 부시고 왔는지 다르기 때문이다. import java.util.*; import java.io.*; public class Main { static int r; static int c; static int k; static int[..
Problem Solving/BFS
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 노드 클래스에 이전에 깼었는지만 기록하면 된다. 그리고 네방향 반복물 돌릴 때 벽일경우 벽이 아닐경우로 나누어서 계산하면 된다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Main { static int n, m; static int[][] board; static..
https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 처음에 시간초과가 났던 문제이다. 첫시도 코드(통과는 함) import java.io.*; import java.util.*; public class Main { static int r; static int c; public static int DSLR(int number,int method){ if(method==0){ return (number*2)%10000; } if(metho..
https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net bfs 두번 쓰는 문제, 몇초(step)을 저장하는 방식은 두가지이다. 이 경우에는 visited에 시간을 기록하는 방법을 쓰면 쉽다. import java.io.*; import java.util.*; public class Main { static int r; static int c; static String[][] map; static int[][] fire_visited ; public static v..
https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 형제 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net import java.io.*; im..
https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net import java.io.*; import java.util.*; public class Main { static int l; public static class Node{ int r; int c; int step; public Node(int r, int c, int step){ this.r=r; this.c=c; this.step =step; } } public static int bfs(No..
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net import java.io.*; import java.util.*; public class Main { static int n; static int m; public static class Node{ int x; int step; public Node(int x, int step){ this.x=x; this.step =step; } } public stati..
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS는 visited를 확인을 q에 삽일할 때 해주면 된다. import java.io.*; import java.util.*; public class Main { static int n; static int m; public static int bfs(int start){ Queue q = new LinkedList(); int[] visited = new int[1..
