CS STUDY

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 이 문제는 BFS 문제이긴 하지만 한가지 조건이 있다. 바로 graph에서 1(벽)인 부분을 깨고 진행할 수 있다는 점이다. 그러므로 visited 배열을 잘 사용해야 하는데 최단거리를 저장하는것이 아닌 1이 만났을때만 count를 올려주는 방법이 좋다. 또한 graph 내에서 0들만 먼저 탐색할 수 있도록(벽을 최소한 부신다고 했다) appendleft 함수를 사용해서 탐색..

출처: https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 위 문제는 기본적인 최단거리 찾기 문제이다. 나는 처음에 DFS로 접근해서 답이 나오지 않았다. 이 문제는 BFS로 풀어야 한다. import collections N,M=map(int,input().split()) q=collections.deque() q.append((0,0)) m=[] for _ in range(N): m.append(list(map(int,input()))) arr=[0]*M visited=[] ..

https://leetcode.com/problems/combinations/ Combinations - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이번 포스팅에선 저번 순열에 이은 DFS로 조합에 대해 풀이해보겠다. 조합은 순열과 달리 원소의 순서가 달라도 구성되어져있는 원소의 종류가 같으면 같다고 처리해야한다. 예를들어 [1,3] 과 [3,1]은 조합에서 같은 것이다. 순열에서 풀이했던 코드와 상당히 유사하다. def combine(n: int, k: i..

https://leetcode.com/problems/permutations/ Permutations - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이번 포스팅에서는 DFS를 이용한 순열에 대해서 정리해 보겠다 순열은 다음 그래프처럼 DFS로 해결할 수 있다. 풀이 방법에는 두가지 방법이 있다. 먼저 재귀구조로 문제를 풀어보겠다. def permute(nums): sol=[] def dfs(index,array): if len(array) == len(num..

https://leetcode.com/problems/number-of-islands/ Number of Islands - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 입력값이 정확히 그래프는 아니지만 사실상 동서남북이 모두 연결된 그래프로 가정하고 동일한 형태로 처리할 수 있으며, 네 방향 각각 DFS 재귀를 이용해 탐색을 끝마치면 1이 증가하는 형태로 육지의 개수를 파악할 수 있다. class Solution: def numIslands(self, grid..

그래프의 각 정점을 방문하는 그래프 순회에는 크게 깊이 우선 탐색(Depth-Frist-Search(이하 DFS))과 너비 우선 탐색(Breadth-First_search(이하 BFS))의 2가지 알고리즘이 있다. DFS는 주로 스택으로 구현하거나 재귀로 구현하며, 이후에 살펴볼 백트래킹을 통해 뛰어난 효용을 보인다. 반면 BFS는 주로 큐로 구현하며, 그래프의 최단 경로를 구하는 문제 등에 사용된다. 아래 그림과 같은 순회 그래프를 살펴보자. 그래프를 표현하는 방법에는 크게 인접 행렬과 인접 리스트의 2가지 방법이 있는데, 이번 포스팅에서는 위 그래프를 인접 리스트로 표현하겠다. 1. DFS graph={ 1:[2,3,4], 2:[5], 3:[5], 4:[], 5:[6,7], 6:[], 7:[3] } ..