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..
Problem Solving/BFS
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..
이 문제는 이것이 코딩테스트다. 152페이지 문제이다. BFS문제를 많이 다뤄 보지 않았어서 시간이 오래 소모 되었던 것같다. DFS,BFS는 양식이 거의 비슷하니깐 틀자체를 기본적으로 몸에 익혀야겠다. 아래는 나의 코드이다. import sys from collections import deque N,M = map(int,sys.stdin.readline().split()) myMap = [] visited=[[False]*M for _ in range(N)] moves = [[1,0],[0,1],[-1,0],[0,-1]] for i in range(N): temp=list(map(int,sys.stdin.readline().split()[0])) myMap.append(temp) def BFS(sta..
