Dev.baelanche

문제가 엄청긴데 요약하자면 그래프에서 A에서 B로 가는데 몇단계를 거치는지 구하라는 얘기이다. 유저가 3명일때 1 : 1->2 , 1->3 2 : 2->1 , 2->3 3 : 3->1 , 3->2 노드 별로 n-1만큼의 경우가 있고 이 경우의 합이 가장 작은 노드의 번호를 구하면 된다. 양방향 그래프를 구현한 후 DFS나 BFS로 간선을 몇번 탔는지 구한다. public class Main { static int n; static int a[][]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokeni..

문제의 특징을 살펴보자. 1. 노드가 향하는 방향은 1가지이다. 2. 순열은 반드시 사이클을 이룬다. 위 특징때문에 각 노드는 반드시 한번만 방문하게 되므로 1차원 배열로도 충분히 구현할 수 있다. public class Main { static int n; static int a[]; static boolean visited[]; static int cnt = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t-->0) { n = sc.nextInt(); a = new int[n+1]; visited = new boolean[n+1]; for(int i=1; i

상, 하, 좌, 우, 위, 아래로 퍼진다는 것만 유의하며 BFS 를 하면 된다. int dh[] = {0, 0, 0, 0, -1, 1}; //위, 아래 int dn[] = {-1, 1, 0, 0, 0, 0}; //상, 하 int dm[] = {0, 0, -1, 1, 0, 0}; //좌, 우 나는 이렇게 해결했다. 처음부터 모두 익어있다면 0, 모두 익지 못한다면 -1이 출력되는 부분을 따로 예외처리 해주었다. int cnt = -1; //기본 카운트 while(!q.isEmpty()) { //로직 수행 cnt++; } for() { //토마토 배열 체크 } //딱 한번 수행되고 멈추었다면 안익은 토마토가 없다는 뜻이므로 0 출력 //토마토 배열을 체크하여 안익은 토마토가 있다면 -1 출력 //모두 익었다..

배열에 대해서 방문한 적이 없고 땅이라면 인접한 땅에 대해서 DFS 를 한다. DFS 한 컴포넌트의 개수를 세어주면 된다. public class Main { static int w; static int h; static int a[][]; static boolean visited[][]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true) { w = sc.nextInt(); h = sc.nextInt(); if(w == 0 && h == 0) break; a = new int[h][w]; visited = new boolean[h][w]; for(int i=0; i

그래프에 대해 공부해 보았다면 DFS 로 풀 수 있는 문제란걸 유추할 수 있다. 연결된 정보를 가지고 문제를 푼다 -> 그래프 문제 만든 그래프로 최단거리, 최소거리를 구해야 한다 -> BFS 그렇지 않다 -> DFS 네트워크 연결이 한방향으로만 되지는 않을것이고 별도의 언급도 없으니 양방향 그래프라고 볼 수 있다. 2차원 배열로 그래프를 만들어 노드마다 연결된 노드 번호를 매겨주고 카운트를 세어주면 된다. 노드 탐색을 할때 연결된 노드를 전부 탐색한 뒤 재귀호출 하는 방식으로 구성하고 싶어서 큐를 이용했다. public class Main { static int n; static int a[][]; static boolean visited[]; static Queue q = new LinkedList(..

아기 상어가 도움을 요청하지 않고 사냥도 안하고 무한정 머무를 수 있으므로 문제에서 요구하는 것은 최소 시간이다. 따라서 BFS로 배열을 순회하면 되겠다. 탐색 조건이 까다로워 BFS 를 "잘" 구현해야한다. *조건 1. 물고기 크기가 상어보다 작아야 잡아먹을 수 있다. 2. 물고기 크기와 상어의 크기가 같다면 크 위치로 이동할 수 있지만 먹을수는 없다. 3. 잡아먹을 수 있는 물고기가 여러마리이면 가장 위쪽의 물고기를 먹는다. 3-1. 3번 조건에서 가장 위쪽에 물고기가 없다면 가장 왼쪽의 물고기를 먹는다. 4. 잡아먹을 수 있는 물고기가 없다면 엄마 상어를 부른다. 필자가 구현할 로직을 아래에 서술하겠다. 1. 아기 상어의 위치에서 BFS 를 한다. 2. 잡아먹을수 있는 물고기가 있으면 잡아먹고 BF..

여타 BFS 문제처럼 1에서 확장하고 -1은 벽으로 취급하여 푼다. 안익은 토마토(0)이 없을때의 카운트를 출력해준다. public class Main { static int m; static int n; static int a[][]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); m = sc.nextInt(); n = sc.nextInt(); a = new int[n][m]; for(int i=0; i

2차원 배열에서 BFS 를 순회하는데 벽을 한 번 부술 수 있다. 방문 정보 배열을 2층으로 구성하여 벽을 부수고 지나갔을 때의 정보와 벽을 안부쉈을때의 정보를 따로 기록한다. 큐에도 벽 부수기에 대한 정보를 담아 한번 부수면 더이상 부술수 없게 한다. public class Main { static int n; static int m; static int a[][]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); a = new int[n][m]; for(int i=0; i