dfs (11) 썸네일형 리스트형 백준 9202 Boggle (파이썬) https://www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net 풀이 이전에 풀었던 백준 전설19585 와 비슷한 문제이다. 이전 문제가 단순히 트라이를 사용하는 문제라면 해당 문제는 트라이와 DFS를 같이 조합해서 푸는 문제이다. 핑계처럼 들리겠지만 오랜만에 알고리즘 푸니까 쉽게 풀지는 못했다... 풀이법은 다음과 같다. 1. 문제에서 주어진 단어들로 트라이를 생성한다. 2. 주어지는 board를 기준으로 모든 칸마다 조건을 만족하면 DFS.. 백준 14620 꽃길 (파이썬) https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 풀이 이 문제는 파이썬의 itertools를 사용해서 combinations를 통해서 푸는 방법과 DFS로 푸는 방법이 있다. 코드 #=================== 조합으로 푸는 방법 =================== # import itertools # feild = [] # answer = int(10e9) # d = [(-1, 0), (1, 0), (0, 1), (0, -1)] # .. [백준] 바이러스 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] = .. [백준] 14500 테트로노미노 (JAVA) 풀이 이 문제를 처음 접근할떄는 어떠한 규칙이 있는지 확인 하였다. 그러나 문득 어느 한점에서 DFS처럼 갈수있는 공간을 하나씩 만들다보면 테트로노미노를 대칭 혹은 회전시킨 도형이 나온다는것을 알아차리고 DFS로 하였다. 물론 이러면서 중복이 발생하는 경우도 있었지만 신경쓰지 않고 진행하였다. 그리고 마지막으로 ㅗ모양을 따로 처리를 해주어야 한다. 또한 중간에 Math.max함수를 사용할수 있음에도 사용하지 않은 이유는 풀이시간이 차이가 나기때문이다. 처음 통과하였을떄는 Math.max를 하였는 결과값이고 두번째는 삼항연산자로 하였는것이다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRead.. [백준] 14502 연구소 (JAVA) 풀이 위의 문제는 BFS와 DFS를 적당히 조합하여 푸는 문제이다. 문제를 푸는 순서는 다음과 같다. 문제에서 벽을 3개를 세워 안전구역의 최대값을 구하라고 하였다. 우리는 벽을 세우고 바이러스를 퍼트리는 일을 한번에 할수 없으니 벽을 먼저 세우고 만약 세운 벽의 개수가 3개이면 바이러스를 퍼트리는 식으로 하였다. 벽을 세우는 과정은 브루트 포스로 처음부터 끝까지 모든 경우의 수를 확인 하였고 바이러스를 퍼트리는 과정은 퍼트리기전 바이러스의 위치를 큐에 전부 넣고 큐에 있는 바이러스 위치를 토대로 하나씩 뽑아 가면서 퍼트릴수있다면 퍼트리고 큐에 추가하는 방식으로 진행하였다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.. [백준] 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.. [백준]1937 욕심쟁이 판다 (JAVA) 풀이 이 문제를 처음보고는 할수있을듯 싶어 고민하였다. 조금 생각하다 내린 나의 결론은 이 문제는 DFS와 Dp를 이용해서 푸는 문제일 것이다. 그도 그럴것이 그래프 탐색과 유사하며 동일한 루트를 여러번 갈수도 있기에 시간을 줄이면 좋으므로 Dp또한 같이 적용시켜야 할것 같았다. 알고리즘의 전체적인 개요는 우선 대나무의 양이 저장되어있는 2차원 배열을 만든다. 그러고 나서 DFS를 적용할것이므로 visite2차원 배열을 만들어준다. 그리고 나서 마지막으로 DP를 2차원배열로 선언하는데 이때 나느 선언할때 값들을 1로 전부 초기화했다. 왜냐면 만약 상하좌우의 좌표의 대나무의 양이(막혀있지 않다고 가정하였을때) 현재 위치에 존재하는 대나무의 양보다 적으면 아무데도 이동할수는 없지만 그래도 적어도 현재 위치한.. [백준] 1182 부분수열의 합 (JAVA) 풀이 살짝 변칙적인 백트랙킹 인듯하다. 이문제에서는 for문이 필요하지 않다. 이해는 코드를 보면 갈것이다. 백트랙킹 문제를 더 풀어봐야 할것 같다. package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main { static int N; static int S; static int count=0; static int Sum; static int[] Num; public static void main(String[] args) throws IOException { BufferedRea.. [백준] 4963 섬의 개수 (JAVA) https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 위의 문제는 예전에 풀었던 백준1012번과 동일하다 문제에서 갈수있는 섬의 개수를 구하라고 했는데 이는 DFS혹은 BFS로 탐색할수있는 섬들의 집합이 몇개나 있는지 물어보는 문제이다. 우선 상하좌우 대각선으로 갈수있는 집합을 만들어주고 그다음 BufferdReader로 읽어서 visit와 map을 초기화 시켜준다. 그 이후 만약 현재 위치가 바다가 아닌 섬이고 미방문한 지역중 섬인 지역.. [백준] 6603 로또 (JAVA) https://www.acmicpc.net/problem/6603 위의 문제는 DFS를 이용한 백트랙킹으로 풀수있다. 처음에는 문제를 계속 풀려고 해도 풀리지가 않아서 타 블로그의 글을 보았다. 그럼에도 잘 이해가 가지않아서 혼자 연습장에 끄적거리보기도 하고 유튜브에 강의를 찾아보기도 하였다. 그러던 중 정말 크게 도움이 된 강의의 주소를 올려놓겠다. https://www.youtube.com/watch?v=Ar40zcPoKEI - 코드없는 프로그래밍님의 강의이다. 아래의 코드를 통해서 내가 몰랐던것들과 새로 이해한것에 대해서 설명을 하겠다. 전역으로는 ary(원소들의 집합), k(집합의 크기), skip(현재 선택한 원소들에 대해서 나타내는 배열)과 출력을 할때 쓰일BufferedWriter를 선언했다.. 이전 1 2 다음
