Dev.baelanche

BFS로 치즈의 외곽을 구하고 반복된 시뮬레이션으로 정답을 도출했다. 1. 주어진 n, m을 n+2, m+2 하여 배열을 만든다. 치즈 외곽 탐색을 위해 편의상 바깥쪽 배열을 한칸씩 여유를 두었다. 2. 배열 탐색을 줄이기 위해 치즈의 개수를 세어 변수에 담는다. 3. 치즈가 녹기 전의 배열을 저장한다. 4. 외곽 치즈를 체크한다. (0, 0)은 무조건 치즈가 없으므로 BFS를 통해 치즈가 없는 부분을 모두 체크한다. (배열 값을 -1로 만들었다.) 5. 치즈 배열 인덱스에서 상하좌우 중 한개라도 -1이면 외곽의 치즈이므로 임의의 큐에 담는다. 6. 큐에 담은 좌표를 모두 0으로 바꾼다. 7. -1로 만든 외곽치즈를 다시 0으로 바꾼다. public class Main { static int n; sta..

문제가 엄청긴데 요약하자면 그래프에서 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..

육지중에 가장 멀면서 빠른 길을 찾으라는 문제이다. 문맥이 참;; 배열 크기가 50*50이니 육지인 인덱스마다 BFS를 해주며 완전탐색하면 된다. public class Main { static int n; static int m; static int a[][]; static boolean visited[][]; static int dx[] = {-1, 0, 0, 1}; static int dy[] = {0, -1, 1, 0}; static int max = 0; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Stri..

백트래킹으로 바이러스를 모두 활성화 해보면서 모든 경우의 수를 체크한다. 시간제한이 굉장히 짧으므로 중복되는 백트래킹이 없어야한다. 예를들어, 바이러스 1번, 2,번 3번 을 활성화 한 후 BFS를 마쳤으면 1번, 3번, 2번 과 같은 경우는 없어야한다. 이는 백트래킹할때 변수를 넘겨주며 현재 활성화 한 바이러스번호 보다 높은 바이러스만을 활성화하게 하면 된다. public class Main { static int n; static int m; static int a[][]; static ArrayList virus = new ArrayList(); static int dx[] = {-1, 1, 0, 0}; static int dy[] = {0, 0, -1, 1}; static int min = Int..

문제가 너무 길어 중략하겠다... 문제는 장황한데 로직 자체는 별거 없다. 삼성 SW 문제들은 기본 탐색 + 문제 해결/구현 조합으로 자주 나오는데 문제에 접근하는것 자체는 어렵지 않아 흥미가 붙는 느낌이다. 문제 진행은 다음과 같다. 1. BFS 로 1회 탐색하며 문제에서 요구하는 대로 미세먼지를 퍼트린다. 2. 공기청정기를 문제에서 요구하는 대로 작동시켜 미세먼지를 뒤로 민다. 3. 입력받은 시간만큼 반복한 후 미세먼지의 양을 출력한다. 미세먼지 확산은 확산 과정에서 합연산으로 먼지가 쌓이므로 먼저 BFS를 1회 마친 후 큐에 담겨있는 노드들을 빼내면서 배열을 다시 채워준다. 그리고 다음 BFS에 미세먼지의 위치들을 큐에 담아 진행한다. 이때 공기청정기의 위치도 잊지말고 채워준다. 공기청정기 순환은 ..

BFS + 구현으로 풀었다. 인구이동을 시작할때 모든 노드에 대해 탐색을 시도해야 하므로 한번의 BFS만을 해서는 안된다. while(b) { cnt++; b = false; allbfs(); } public static void allbfs() { visited = new boolean[n][n]; for(int i=0; i

문제에 나와있는 규칙을 잘 지키며 BFS를 수행해야 한다. 주의할 점은 따로 없어 코드에 주석을 달아놓았다. 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]; int r = sc.nextInt(); int c = sc.nextInt(); int d = sc.nextInt(); for(int i=0; i

최소 회수를 출력하라길래 BFS로 풀었다. 1. 4자리수의 소수 배열을 저장해 놓는다. 2. 매 탐색시 각 자리수를 0~9로 바꾸며 소수인지 아닌지 체크하며 소수이면 큐에 담는다. 3. 만들어진 수와 입력받은 수가 같으면 정지한다. 4자리수가 안되는 수는 모두 소수가 아니라고 저장하여 예외처리했다. 그리고 따로 방문이력을 담은 배열을 만들어 체크해 주어야 불가능한 경우를 알아낼 수 있다. public class Main { static boolean prime[] = new boolean[10000]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamRe..