알고리즘/백준
-
[백준] 14502. 연구소알고리즘/백준 2021. 4. 5. 01:56
문제 출처 https://www.acmicpc.net/problem/14502 문제 설명 2차원 좌표계에 벽과 바이러스가 있다. 바이러스는 확산되지만 벽은 통과할 수 없다. 3개의 벽을 더 세워서 바이러스를 최대한 억제해라. 문제 풀이 지도가 최대 8x8로 아담하다. 3개의 벽을 세울 수 있는 모든 경우의 수를 도전해봐도 충분할 것이다. 3개의 벽을 세웠다면 바이러스를 확산시키고 안전 구역을 센다. 안전 구역의 최댓값을 출력한다. 왜 모든 경우의 수를 도전해봐도 충분한가? 최악의 경우 8x8에 3개의 벽을 세울 수 있는 경우의 수는 64C3 = 41,664 이고 8x8의 지도를 41,664번 순회한다면 2,666,496회의 연산이 필요하다. 이런 식의 어림짐작으로 1억을 넘지않는다면 백준의 1초를 통과할..
-
[백준] 4963. 섬의 개수알고리즘/백준 2021. 4. 4. 23:02
문제 출처 https://www.acmicpc.net/problem/4963 문제 설명 바다와 땅이 있다. 인접한 땅들은 한 개의 섬이다. 섬의 개수를 세어라. 문제 풀이 완전 탐색으로 땅을 찾는다. 땅을 찾으면 인접한 모든 땅을 너비 우선 탐색으로 방문 표시한다. 땅을 찾은 횟수가 섬의 개수가 된다. 코드 코드 해설 public static void main(String[] args) throws IOException { readInput(); while (!(R == 0 && C == 0)) { int answer = getIslandCount(); System.out.println(answer); readInput(); } } 항상 메인문은 심플하게. 1. 입력을 받는다. 2. 계산한다. 3. 출력..
-
[백준] 7562. 나이트의 이동알고리즘/백준 2021. 3. 31. 01:55
문제 출처 https://www.acmicpc.net/problem/7562 문제 설명 나이트는 체스 말의 나이트처럼 움직인다. 2차원 좌표계에서 탐색하는 문제다. 문제 풀이 bfs로 해결한다. 코드 코드 해설 public static void main(String[] args) { readInput(); for (int tc = 0; tc < testCase; tc++) { int answer = bfs(tc); System.out.println(answer); } } readInput()에서 모든 입력을 받는다. 테스트케이스만큼 bfs를 연산하고 결과를 출력한다. Queue queue = new LinkedList(); queue.offer(knight[tc]); while (!queue.isEmpt..
-
[백준] 1657. 숨바꼭질알고리즘/백준 2021. 3. 30. 22:59
문제 출처 www.acmicpc.net/problem/1697 문제 설명 1차원 좌표계에서 경로를 탐색하는 문제다. 문제 풀이 bfs로 풀었다. 현재 있는 점에서 갈 수 있는 모든 방향을 큐에 넣는다. 큐에 목적지가 있다면 결과를 출력하고 종료한다. 코드 코드 해설 public static void main(String[] args) { readInput(); int answer = bfs(); System.out.println(answer); } 메인은 항상 직관적으로 구성한다. 1. 입력을 받는다. 2. 연산한다. 3. 결과를 출력한다. public static int move(int x, int method) { switch(method) { case 0: return x - 1; case 1: r..