[백준] Python,Java로 풀기📖/DFS&BFS
백준 13565(침투) - Python(파이썬) - DFS
백준 13565(침투) - Python(파이썬) - DFS
2022.06.2713565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 예제 풀이 outer side 0⬇️ 1 0⬇️ 1 0⬇️ 1 0⬇️ 1 0➡️ 0➡️ 0⬇️ 0 0❌ 1 1 1 0❌ 1 1 0 0 0 1 1 0 0 1 0 1 1 inner side 이렇게 outer side에서 시작해서 inner side로 나가야하지만 중간에 전류가 통하지 않는 물질땜에 멈추게 된다. outer side 1 1 0 0 0⬇️ 1 1 1 0 1 1 0 0➡️ 0⬇️ 0 0 0 0 0 1 1 0⬇️ 0 1 1..
백준 2309(일곱 난쟁이) - Python(파이썬) - Combinations 사용,브루트포스
백준 2309(일곱 난쟁이) - Python(파이썬) - Combinations 사용,브루트포스
2022.06.172309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 💬 처음 생각한 풀이(Python(파이썬)) 단순하게 python으로 풀 때 ① combinations 함수를 사용하여 일곱명 뽑기 ② 합이 100인 경우를 찾아 출력 *여기서 주의할점은 sort는 원본을 변경하지만, sorted는 원본을 변경하지 않는다. * tuple: sort()함수를 사용하지 못하므로 -> sorted를 사용하여 정렬 후 출력 💻파이썬(Python) import sys from itertools import combinations arr=[] #난..
백준 2667(단지번호 붙이기) - Python(파이썬) - BFS
백준 2667(단지번호 붙이기) - Python(파이썬) - BFS
2022.06.142667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 예제 설명 이렇게 생긴 지도가 있다고 할 때 선분 하나를 공유하고 있는 경우에는 같은 단지이다. 출력으로 단지의 개수를 구하고 단지 안에 속하는 집의 수를 오름차순으로 정렬하여 출력하도록 한다. 문제 풀이 1) dfs 방식으로 풀기 1️⃣ dfs 함수 만들기 ① 재귀함수를 이용해서 풀기 때문에 함수를 실행 전에 지도안에 포함되는지를 확인 -> 아닐 경우 , return False ② 지도안에 포함될 경우 지도 안에 1로 표시된 집인지 확인 -> 아닐 경우, ret..
백준 2178(미로 탐색) - Python(파이썬) - BFS
백준 2178(미로 탐색) - Python(파이썬) - BFS
2022.06.142178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 예제 설명 이런식으로 문제에서 주어진 배열에 1이 적혀있고 인접한 칸으로만 이동이 가능하다. 따라서 BFS 문제로 문제는 이동할때마다 이동한 곳(array[y][x])의 값보다 +1시켜서 마지막 array[4-1][6-1]의 값을 구하면 된다. ( https://coooco.tistory.com/32 ) 💻 Python 처음 한 풀이 import sys from collections import deque n,m = map(int,sys.stdin.readline().split()) array..
백준 24479(깊이 우선 탐색 1) - Python(파이썬),Java(자바) - DFS
백준 24479(깊이 우선 탐색 1) - Python(파이썬),Java(자바) - DFS
2022.06.01예제 문제 설명 1. 1번 노드를 처음 시작하므로 첫번째 방문으로 visted 되었다고 표현하기 위해서 visted[1] 1로 바꿈 2. 1번 노드와 연결된 2번, 4번 중에 2번 노드가 더 작으므로 2번 노드 방문 -> 2번 노드 2번째로 방문하였으므로 visted[2] 2로 변경 3. 2번 노드와 연결된 1번,3번,4번 중 방문하지 않은 노드 중에 작은 값인 3번 노드 방문 -> 3번 노드 3번째로 방문하였으므로 visted[3] 3으로 변경 4. 4번 노드와 연결된 1번,3번,4번 노드 중 방문하지 않은 노드들이 없다.끝 그러면 5번 노드는 시작 노드 1번으로부터 방문하지 못하는 노드이므로 0으로 그냥 명시 ( 조건에서 방문 못하는 노드는 0이라고 명시하라고 하였으므로) 결론: 출력은 visted에..
백준 18352(특정 거리의 도시 찾기) - Python(파이썬) -BFS
백준 18352(특정 거리의 도시 찾기) - Python(파이썬) -BFS
2022.05.2518352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 방법 모든 도로의 거리가 1이므로 -> bfs 가능하다. ① graph(노드와 간선을 나타내는 그래프) (연결 여부 확인용)으로 사용한다 -> a와 b가 연결되었다고 가정하면 graph[a] = [b] 이렇게 있도록. ② 거리 테이블을 표현하는 테이블 하나 선언하기 (distance) , 이때, 초기값들은 모두 -1이도록 선언 ③ 시작노드부터 시작하여서 연결된 노드들의 값이 -1인경우(..
백준 16948(데스나이트) - Python(파이썬),자바(Java)
백준 16948(데스나이트) - Python(파이썬),자바(Java)
2022.05.2416948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net BFS - duque 메서드 - Python(파이썬),Java(자바) DFS 설명 스택, 큐, 재귀함수, DFS 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 탐색 알고리즘으로 DFS, BFS , 이 두 알고리즘을 이해하기 위해서 스택, 큐, 재귀 함 coooco.tistory.com 풀이 방법 ① 이차원 배열로 nxn graph 생성 ( -> 이동..
백준 4936(섬의 개수) - BFS 풀기
백준 4936(섬의 개수) - BFS 풀기
2022.05.21BFS - duque 메서드 - Python(파이썬),Java(자바) DFS 설명 스택, 큐, 재귀함수, DFS 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 탐색 알고리즘으로 DFS, BFS , 이 두 알고리즘을 이해하기 위해서 스택, 큐, 재귀 함 coooco.tistory.com import sys from collections import deque dw=[-1,-1,-1,0,0,1,1,1] dh=[-1,0,1,-1,1,-1,0,1] def bfs(graph,h,w): queue=deque() queue.append((h,w)) while queue: h,w = queue.popleft() for i in range(8): nw = w+dw[i] nh = h+..
백준 14716(현수막) - 파이썬(Python),자바(Java) - DFS(재귀함수),sys.setrecursionlimit(10**6),BFS
백준 14716(현수막) - 파이썬(Python),자바(Java) - DFS(재귀함수),sys.setrecursionlimit(10**6),BFS
2022.05.2014716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net * 재귀함수 문제 시에는 sys.setrecursionlimit(10**6)을 상단에 적어준다. 파이썬의 기본 재귀 깊이 제한이 1000으로 작은 편이기 때문에 런타임 에러 발생한다. graph=[] for i in range(m): graph.append(list(map(int,sys.stdin.readline().split()))) graph=[list(map(int,sys.stdin.readline().split())) for _ in range(m)] 둘은 동일하다. 1. DFS로 푼 경우 스택, 큐, 재귀함수, DFS 탐색(Search) : 많은 양의 데이..
백준 1260(DFS와 BFS) - DFS & BFS
백준 1260(DFS와 BFS) - DFS & BFS
2022.05.18DFS 설명 스택, 큐, 재귀함수, DFS 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 탐색 알고리즘으로 DFS, BFS , 이 두 알고리즘을 이해하기 위해서 스택, 큐, 재귀 함수를 알아야한다. 참고자료. https: coooco.tistory.com BFS 설명 BFS - duque 메서드 - Python(파이썬),Java(자바) DFS 설명 스택, 큐, 재귀함수, DFS 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 탐색 알고리즘으로 DFS, BFS , 이 두 알고리즘을 이해하기 위해서 스택, 큐, 재귀 함 coooco.tistory.com 내가 푼 풀이법 입력한 값들을 연결된 노드를 저정하도록 그래프를 만든다. graph..