출저 : https://www.acmicpc.net/problem/1389 "다익스트라,BFS,DFS 다~~" 다익스트라를 연습할 수 있는 좋은 문제 인 듯, 일단 다익스트라는 BFS를 활용해 시작지점으로부터 연결된 모든 노드로 가는 최소값을 찾는 알고리즘이다. ( 단, 다익스트라는 가중치가 각각 다른 경우에 유용하며, 이 문제에서는 가중치가 1이므로 그냥 BFS 혹은 DFS 탐색하면됨...) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869import java.io.BufferedReader;import java.io.IO..
출저 : https://www.acmicpc.net/problem/2583 "BFS" 영역을 나 누 자 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Collections;import java.util.LinkedList..
출저 : https://www.acmicpc.net/problem/2234 "BFS 그리고 비트마스킹(필수는아님..)" 비트마스킹을 사용하지 않고도 0 ~ 15 까지의 숫자별로 가능한 방향을 이차원 배열로 정의해줘서 풀면됨... 하지만 아래 풀이는 비트마스킹 써씅ㅁ. solve1()을 통해 아래 두개의 답을 구할 수 있다. 1. BFS를 돈다.2. 1번 BFS를 돌면서 각 방의 size가 구해지므로 최대값을 비교해 구한다. 마지막 문제에 대한 답을 구하는게 관건인듯 하다. 나는 1,2 번을 구하면서 새로운 int[][] arr 을 정의해서 이곳에 0~ 방의 개수 까지 카운터를 마킹했다.(영역 나누기 처럼) 동시에 각 index마다 방의 크기를 ArrayList에 저장해두었다. 그 후에 새로 정의한 맵 a..
출저 : https://www.acmicpc.net/problem/3055 "순서를 잘 생각한 BFS 두개." 먼저 물과 고슴도치를 이동 시키기 위해 두개의 Queue를 준비한다. 두개의 queue는 각 time 마다. 상하좌우로 이동할 것이다. 이때 물과 고슴도치 중 어떤 것을 먼저 움직여야 할까? 문제에 조건에 따르면 다음 시간에 물이 찰 곳에는 고슴도치가 이동하지 못한다고 했으므로, 물을 먼저 이동 시켜주고, 물이 찰 곳에 고슴도치가 이동하지 못하도록 해주어야 한다. (만약 고슴도치가 수영을 N 번 할 수 있다고 한다면 문제가 어려워 질거같다... ) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546..
출저 : https://www.acmicpc.net/problem/4963 "BFS 탐색, 단지번호 붙이기" BFS 탐색을 통해 각각 떨어져있는 섬의 개수를 체크하는 것이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;impo..
출저 : https://www.acmicpc.net/problem/2206 "상태 공간에 대한 정의가 중요" 이 문제에서 주의해야할 건 딱 하나... 특정 지점 (x,y) 에 벽을 뚫고 왔느냐, 벽을 안 뚫고 왔느냐는 엄연히 다른 경우라는 것. 따라서 이 경우를 모두 탐색 해주면 되겠다. visited[X 좌표][Y 좌표][벽을 뚫고온 횟수] 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687import java.io.BufferedReader;import jav..
출저 : https://www.acmicpc.net/problem/1963 "소수를 구하고 BFS를 돌리며 자리수를 잘 체크" 먼저 BFS 탐색 전에 10000 이하의 수의 소수 여부를 저장하고 있는 boolean[] nonPrime 배열을 셋팅한다. 그 후에 BFS 탐색을 통해 목적지에 도착하는지 체크한다. 가능 / 불가능 여부는 boolean형 ok 변수를 통해 체크했다. BFS 탐색중 int origin 변수를 써서 변경한 값을 원래로 되돌려야함을 주의한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727..
출저 : https://www.acmicpc.net/problem/2573 "BFS" 전체 맵을 탐색하며 빙산이 있는 곳에 상하좌우를 탐색하여 물이 있는 칸의 개수 만큼 빼주는 것은 쉽다. 이때, 유의해야 할점은 같은 시간대에 앞서 녹아버린 빙하가 0이 되면 이 값이 다른 빙하의 감소에 영향을 끼칠 수 있다는 것이다. 이런 부분을 처리하기 위해 감소 시 0 이 되는 빙하는 바로 감소시키는 것이 아니라 값을 그대로 놔두고, 별도 자료구조에 저장해 놓고, 전체 맵을 다 탐색한 이후에 0 이 되는 빙하들을 처리해 주어야 한다. 해당 풀이에서는 별도의 큐를 두어 관리했다. 더해서 또하나 놓치기 쉬운 조건은 빙하 그룹이 0이 되지 못하는 경우이다. 즉, 한 번에 모든 빙하가 다 녹아버리는 경우이다.이부분은 빙하 ..
출저 : https://www.acmicpc.net/problem/11967 "상태 공간에 대한 정확한 이해가 필요" 먼저 상태 공간에 대한 정의가 중요하다. 나는 방문 여부를 체크하는 visited와 해당 방에 불이 켜져있는지를 체크하는 light 두 개의 2차원 배열을 두었다. 그리고 방에 있는 스위치 정보는 x,y 좌표를 x*N +y 를 사용해 index로 변환해서 저장했다. 따라서 아래와 같은 변수를 사용한다. ArrayList[] list; A 방에 도착해서 B 방에 불을 켰고 B까지 갈 수 있다면 가정했을 때, 그 방을 기점으로 해서 다시 탐색을 시작해야함을 주의한다. 나는 처음에 불을 다시 켰을 때 visited 배열을 초기화 시켰는데, 통과는 했으나 시간이 오래 걸려 그냥 q에 넣어주는식으..
출저 : https://www.acmicpc.net/problem/14226 "BFS, visited 배열을 잘 생각하자.." 해당 문제를 풀다가 visited[] 배열을 어디까지 할까 고민하다.... 1001 로 해서 런타임 에러, 2002 로 했더니 틀렸다.... 잘 생각해보니 특정 이모티콘 길이에 도착했을 때, 버퍼에 1글자를 가지고 오는것과 10글자를 가지고 오는 것은 다른 경우... 따라서 이차원 배열을 방문체크 배열로 해야한다. visited[이모티콘길이][버퍼의길이] 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061import java.io..
- Total
- Today
- Yesterday