BFS

백준 1600번 말이 되고픈 원숭이 [ Java ]

1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[] dx = new int[]{0, 1, 2, 1, 2, 1, 0, -1, -2, -1, -2, -1..

백준 2206번 벽 부수고 이동하기 [ Java ]

2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()..

백준 2146번 다리 만들기 [ Java ]

2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 제가 사용한 방법은 처음에 BFS로 라벨링을 했습니다. 그리고 그 라벨마다 따로 BFS를 돌려주어 다른 섬을 만나면 거리를 구해 최소값 구하기 연산을 하여서 각 섬에서의 최소거리를 비교하였습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRea..

백준 5427번 불 [ Java ]

5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 이전에 풀었던 4170: 불!과 동일한 문제였습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[] dx = new int[]{1, 0, -1, 0}; int[] dy =..

백준 11967번 불켜기 [ Java ]

11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[] dx = new int[]{1, 0, -1, 0}; int[..

백준 13913번 숨바꼭질4 [ Java ]

13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 기본 BFS 코드에서 방문배열 말고 parent 배열을 추가해주었습니다. import java.util.*; public class Main { public static void main(String[] args){ Queue Q = new LinkedList(); Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int K = sc.nextInt(); int[] dist =..

백준 13549번 숨바꼭질 3 [ Java ]

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS로 풀었습니다. 가중치가 동일하지 않은 정점을 이동하기 때문에 Q에 넣는 순서가 2배수 -1 +1로 이동하지 않으면 틀리는 문제였습니다. 아직 이러한 유형을 완벽하게 이해하진 못해서 공부가 더 필요할 것 같습니다. import java.util.*; public class Main { public static void main(String[] args){ Queue Q = new LinkedList(); Scanner sc ..

백준 6593번 상범 빌딩 [ Java ]

6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net import java.util.*; import java.io.*; public class Main { static int L, R, C; static int[] dx = new int[]{1, 0, 0, -1, 0, 0}; static int[] dy = new int[]{0, 1, 0, 0, -1, 0}; static int[] dz = new int[]{0, 0, 1, 0, 0, -1}; static String[][][] building; static Queu..

백준 2573번 빙산 [ Java ]

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 기존에 BFS 기본 코드에서 새로운 melt라는 새로운 배열을 추가해 빙산의 영역기준으로 네 방향에 값들이 0보다 작거나 같으면 이후에 빼주는 코드를 작성했습니다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new Input..

백준 5014번 스타트링크 [ Java ]

5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); Queue Q = new Linke..