BFS (11) 썸네일형 리스트형 백준 16988 Baaaaaaaaaduk2 (Easy) (파이썬) https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net 문제를 풀지 못하여 다른 블로그의 글을 참고하였으나...가독성이 떨어지고 불필요한 코드가 있어 고생했다. 나같은 사람들이 없기를 바라면서 글을 정리한다. 풀이 이 문제는 BFS와 조합탐색을 이용해서 해결하는 문제이다. 문제를 해결하는 방법은 다음과 같다. 상대측 돌의 그룹을 찾고 만약 상대측 돌의 그룹에 인접해 있는 빈 칸이 2개 이하이면 해당 그룹과 인.. [백준] 바이러스 2606 파이썬 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 설명 해당 문제는 단순히 그래프탐색을 해서 방문 가능한 노드가 총 몇개인지 확인하는 문제였다. 나는 이전에 DFS, BFS문제를 n x n으로 취급해서 문제를 풀었으나 그렇게 하면 시간복잡도가 상당히 높아지기에 인접리스트꼴로 문제를 풀었다. from collections import deque def bfs(graph, visit): q = deque() q.append(1) visit[1] = .. [백준] 2606 바이러스 (JAVA) https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 이 문제는 그래프를 그리고 DFS혹은 BFS중 원하는것으로 하나를 선택해 탐색해 방문한 노드의 개수를 구하면된다. 나는 여기서 ArrayList속 ArrayList를 넣어 인접연결리스트를 구현하여 그래프를 구성했다. 그리고 만들어지 그래프에서 (1에서 시작하여) 현재위치의 노드에서 인접한 노드들의 번호를 큐에 넣는다. 그리고 큐에서 차례대로 뽑아서 만약 방문하지 않았다면 방문처리를 하고 위의 작업.. [백준] 14502 연구소 (JAVA) 풀이 위의 문제는 BFS와 DFS를 적당히 조합하여 푸는 문제이다. 문제를 푸는 순서는 다음과 같다. 문제에서 벽을 3개를 세워 안전구역의 최대값을 구하라고 하였다. 우리는 벽을 세우고 바이러스를 퍼트리는 일을 한번에 할수 없으니 벽을 먼저 세우고 만약 세운 벽의 개수가 3개이면 바이러스를 퍼트리는 식으로 하였다. 벽을 세우는 과정은 브루트 포스로 처음부터 끝까지 모든 경우의 수를 확인 하였고 바이러스를 퍼트리는 과정은 퍼트리기전 바이러스의 위치를 큐에 전부 넣고 큐에 있는 바이러스 위치를 토대로 하나씩 뽑아 가면서 퍼트릴수있다면 퍼트리고 큐에 추가하는 방식으로 진행하였다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.. [백준] 1697 숨바꼭질 (JAVA) 풀이 처음에 이 문제를 보고 어떠한 규칙을 찾기위해 노력을 했었다. 그러다 문득 바이너리 서치처럼 한번에 하나씩 하면 될것 같다는 생각이 들어 바이너리 서치로 접근을 해보았다. 그러나 바이너리 서치는 +1-1 *2중 무엇이 최적인지 몰랐고 그리디 알고리즘도 맞지 않았다. 그리하여 어떻게 하면 좋을까 생각을 하다 그냥 시간 생각하지말고 무작정 시간을 더하면 되지않을까? 라는 생각을 하게 되었고 그러한 생각을 꾸준히 하다보니 단순히 +1, -1, *2를 해서 특정배열에 담으면 될것 같다는 생각을 하게 되었고 이는 곧바로 정답으로 가게 되었다. 풀이의 발상은 단순하다 만약 현재의 위치가 x라면 x-1, x+1 x*2의 위치에 현재의 시간+1을 더하고 queue에 집어넣는것이다. 그러고 전부 끝나면 현재 que.. [백준] 7576 토마토 (JAVA) 풀이 이 문제는 이 전에 풀었던 미로탐색(2178)과 궤를 같이 하는 문제이다. 나는 미로탐색처럼 간단할줄 알고 덤볐으나 생각할게 조금있었다. 우선 이 문제에서는 시작점이 주어지지 않았으며 하루가 지날때 마다 영향을 받는 토마토는 다양해서 조금 더 생각한것 같다. 그리고 반복문을 생각보다 많이 돌려 문제를 풀면서 시간초과를 많이 신경 썼다. 알고리즘은 다음과 같다. 처음에 box라는 2차원 배열에 토마토의 위치등을 저장할때 토마토가 있는 곳들, 즉 1로 입력값이 주어지는 위치는 바로바로 큐에 집어넣었다. 그리고 저장이 전부 끝난후에는 바로 BFS함수로 들어가서 그래프 탐색을 진행하였다. 참고로 왜 DFS가 아닌 BFS를 사용했는지 궁금하다면 https://goto-pangyo.tistory.com/23 .. [백준] 2667 단지번호붙이기 (JAVA) 풀이 이 문제는 단순히 DFS혹은 BFS로 전부 탐색하면서 각각의 cluster가 몇개가 있는지 있다면 그 cluster에 존재하는 원소들의 값을 바꿔나가면서 탐색이 끝나면 각 클러스터는 몇개이고 cluster의 원소수는 몇개가 있는지 출력하면 되는 문제이다. 범위도 작기때문에 시간 걱정없이 풀면 될듯하다. 코드 import java.io.*; import java.util.ArrayList; import java.util.Collections; import java.util.List; class Main{ public static int [][]map; public static boolean [][] visited; public static int []dr_x = {-1, 0, 1, 0}; public.. [백준] 2178 미로탐색(JAVA) 풀이 학교 알고리즘 시간에 배웠던 미로탐색 문제인줄 알고 단순히DFS로 접근해서 모든경로의 이동수를 리스트에 저장하여 그중 가장 작은 수를 출력할려고 했다. 그러나 시간초과로 인해. 어떡게 풀어야 좋을지 몰랐다. 그래서 찾아보고 그러니 정답은 DFS가 아닌 "BFS"였다. 그러면서 다른 블로그에서는 최단, 최소를 찾을때는 BFS를 통해 구한다고 하여서 왜 그런지 몰랐다. 그러다 어느 블로그를 찾게 되었고 그 곳에 자세한 설명이 있었다. 간략하게 설명을 하면 BFS에선 간선(u,v)를 통해서, 정점 v를 처음발견해 큐를 넣었다고 가정한다. 이때, 시작점에서 v까지의 최단거리는 distanc[v]는 , 시작점에서 u까지의 최단거리 distance[u]에다가 1을 더한것이다. 조금더 풀어쓰자면 1. dista.. [백준] 7562 나이트의 이동 (JAVA) 풀이 위의 문제는 BFS의 정석이라고도 할수있는 문제이다. 그렇다고 풀었는건 아니다... 문제에서 주어지는 나이트의 최단이동경로에 초점을 두어 최단경로를 구하는 알고리즘을 생각하다 보니 풀지 못하였던 것 같다. 그냥 다음으로 이동할때 이동하기전의 이동횟수에 하나씩 더해가다 어느 순간 goal의 좌표와 현재 좌표가 같게 되면 그때의 이동횟수를 출력하면 문제는 풀린다. 살짝 dp와도 비슷한 점이 있는것 같다. 느낀점은 구현만 확실히 해놓으면 부담없이 전부 탐색하면 될듯하다. package com.company; import java.io.*; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class .. [백준] 4963 섬의 개수 (JAVA) https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 위의 문제는 예전에 풀었던 백준1012번과 동일하다 문제에서 갈수있는 섬의 개수를 구하라고 했는데 이는 DFS혹은 BFS로 탐색할수있는 섬들의 집합이 몇개나 있는지 물어보는 문제이다. 우선 상하좌우 대각선으로 갈수있는 집합을 만들어주고 그다음 BufferdReader로 읽어서 visit와 map을 초기화 시켜준다. 그 이후 만약 현재 위치가 바다가 아닌 섬이고 미방문한 지역중 섬인 지역.. 이전 1 2 다음 목록 더보기
