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..
Problem Solving/BFS
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net import java.io.*; import java.util.*; public class Main { static int n; static int m; static int[][] map; static int[] move_r = new int[]{1,0,-1,0}; static int[] move_c = new int[]{0,1,0,-1}; public static class Node{ public int r; public in..
https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 맵이외에 얼음을 따로 관리 해주어서 시간복잡도를 줄일 수 있다. 문제에서 얼음칸의 수를 제한시켜주기 때문에(이런게 힌트인 경우가 있다.) 가능 리스트에서 원소를 삭제할 때 순서가 상관없다면 맨뒤에 것을 해당 인덱스에 집어넣고 맨뒤에 거를 지우면(맨뒤는 O(1)) 시간복잡도를 낮출 수 있다. import java.util.*; import java.io.*; public class Main {..
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net import java.util.*; import java.io.*; public class Main { static List[] graph; static boolean[] visited; public static int bfs(int start){ int count = 0; Queue q = new LinkedList(); q.add(start); while(q.size()>0){ int node = ..
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net import java.util.*; import java.io.*; public class Main { static List[] graph; static boolean[] visited; public static boolean bfs(int start){ boolean check = false; Queue q = new LinkedL..
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net import java.util.*; import java.io.*; public class Main { static List[] graph; static List ans_dfs; static List ans_bfs; static boolean[] visited_dfs; static boolean[] visited_bfs; public static void df..
https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 난이도: 실버1 소요시간: 35분 문제를 보자마자 다익스트라를 써야하나 라는 생각이 들었다. 그러나 오늘 풀 주제는 bfs였기에 bfs로 풀었다. 풀고나니 최단거리문제이면서 모든 거리가 1이라면 bfs를 써도된다는 것을 깨달았다. 앞으로 전형적인 최단거리 문제라도 거리가 1이라면 bfs도 고려를 해보아야겠다. 내일은 최단거리로도 한번 풀어보아야겠다...
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 난이도: 실버2 소요시간: 45분 아래는 나의 코드이다. nq 변수에 값을 잘못 저장하여 에러잡느라 시간을 예상치 못하게 많이 잡아 먹었다... import sys from collections import deque T = int(sys.stdin.readline()) move=[[1,0],[-1,0],[0,1],[0,-1]] def BFS(start): que= deque([start]) if visite..
