DFS

백준 1987 파이썬 풀이 (알파벳, DFS)

기존에 DFS,BFS문제는 주어진 미로에서 가장 짧은 길을 찾거나 걸리는 시간을 주로 구했다. 그런데 이번 문제는 미로가 아닌 각 칸에 알파벳이 주어질때 가장 멀리까지 가는 경우 몇칸이나 지나갈 수 있는지 구하는 것이다. 기존과 달리 모든 경우를 살펴보아야 구할 수 있다. 1. DFS로 각 칸은 상하좌우 확인한다. 2. 이때까지 지나온 알파벳과 중복되지 않으면 갈 수 있다.(즉, 해당 경로 혹은 지나왔는지 체크가 되어 있어야 한다.) 이렇게 2가지 조건을 통해 코딩을 진행했다. r, c = map(int, input().split()) M = [] for i in range(r): tmp = list(input()) M.append(tmp) alpha = [0]*26 alpha[ord(M[0][0])-6..

백준 1012 풀이 (유기농 배추, DFS, 행렬)

2667번과 아주 흡사하다.(guccin.tistory.com/89?category=977502) 그나마 다른점은 정사각형 행렬이 아니라 직사각형 행렬이라는점 뿐이다. 그래서 2667의 DFS함수를 그대로 가져와서 사용할 수 있었다. 코드는 2667과 거의 유사하고 다른점은 배추의 포인트를 직접 갱신 시켜준다는 점과 패딩을 직사각형에 맞춰주는 것 밖에는 없다. 그래서 2667을 이해하면 그냥 껌이 되버리는 문제이다. 풀이 쓰는 시간이 아까우니 바로 코드를 첨부한다. def DFS(i, j, L): stack = [(i,j)] out = [] while stack: t = stack.pop() a,b = t if t not in out: out.append(t) L[a][b] = 0 # 지워버려 #위쪽 오..

백준 2667 단지번호붙이기 (DFS, 그래프 탐색)

이번 문제는 생각보다 쉽게 풀렸다. DFS의 기본 코딩 구조를 알면 바로 대입이 가능한 문제였다. 문제는 1이 집들이고 붙어 있는 집끼리 단지를 조성한다. 그리고 단지의 개수를 확인하고 단지별 개수를 오름차순으로 출력하는 문제이다. 이 문제를 풀기 위해서는 뇌피셜로 필요하다고 생각되는 요소를 정리해 보았다. 1. DFS를 스택을 활용하여 코딩을 구현할 수 있는지 2. DFS로 행렬들의 인접을 어떻게 파악할건지 3. 다음 단지는 어떻게 찾을건지 우선 DFS를 스택을 활용하여 코딩하는건 넘어간다. 그럼 2번 DFS로 행렬들의 인접을 어떻게 파악할건지 생각해본다. 현재 (0,1)에서 가장 먼저 집이 발견된다. 문제는 동서남북 모두 확인하여 인접한 행렬을 확인해야 하는데 위에는 접근할 수가 없다. 따라서 에 패..

백준 2606 바이러스 (DFS)

이번에는 저번에 공부한 것을 토대로 DFS를 구현하는 문제이다. 오히려 저번 문제보다 쉬운게 함정이다. 1번 컴퓨터가 감염될때 감염되는 컴퓨터의 수는 4이다. 따라서 숫자만 구해주면 된다. DFS로 풀게되면 1->2->3->5->6순으로 가게 된다. 그런데 우리는 순서는 중요하지 않아서 stack에 넣어줄때 그냥 때려 넣기만 하면 된다. 따라서 1260 문제 (guccin.tistory.com/87)보다 쉽게 코딩이 가능하다. n = int(input()) m = int(input()) graph = {} for i in range(m): a,b = map(int, input().split()) if a not in graph: graph[a] = [b] else: graph[a].append(b) if..

백준 1260 풀이 (DFS, BFS, 그래프 탐색)

이번 문제는 그래프 탐색 문제이다. 그래프가 주어지면 이것을 DFS,BFS방식으로 탐색하여 순서를 나타내면 된다. DFS, BFS의 개념은 알고 있었지만 막상 코딩으로 짜려니 상당히 헤매었다. DFS를 설명하자면 깊이 우선 탐색방법으로 깊게 들어가는 가며 탐색하는 방법이다 원리는 구글에 자세히 나온다. 처음 도움을 받은 곳은 www.youtube.com/watch?v=_hxFgg7TLZQ 로 영상을 보고 대강 이해를 하고 코드를 짜기 시작했다. 간단히 설명하자면 DFS => stack으로 탐색 가능. 연결되는 노드를 차례로 스택에 저장 BFS => queue로 탐색 가능. 연결되는 노드를 차례로 큐에 저장 자세한 로직은 유튜브를 참고하면 될것이다. 물론 유튜브 과정 그대로 코딩을 하려니 코드가 길고 더러..