https://www.acmicpc.net/problem/14502 문제설명바이러스의 확산을 막기 위해서 연구소에 벽 세우기벽을 세운 뒤 바이러스가 퍼질 수 없는 안전 영역의 최댓값 구하기   문제해결조건연구소의 크기 : N x M 직사각형 (직사각형은 1 x 1 크기의 정사각형으로 나누어져 있다.)연구소의 구성 : 빈 칸(0), 벽(1), 상하좌우로 퍼지는 바이러스 (2)새로 세울 수 있는 벽은 무조건 3개로직현재 빈 칸들 중 3개를 선택해서 벽 세우기 (조합 이용)바이러스를 퍼뜨리는 역할을 하는 BFS 실행, board 모두를 확인해야 하므로 바깥 for문 필요확산 후 안전영역 개수 세고 최댓값 갱신벽 되돌리기row_len, col_len = map(int, input().split())board =..

https://leetcode.com/problems/shortest-path-in-binary-matrix/description/ 문제설명nxn으로 구성된 행렬 grid가 주어질 때, (0,0)에서 (n-1,n-1)로 가는 가장 짧은 길의 길이를 구해라. 갈 수 없으면 -1. 0으로 구성된 칸에만 갈 수 있다.  문제해결가장 짧은 길이를 구하는 거니까 BFS 사용방향 주의하자 ! 4방향이 아니라 8방향으로 주어짐현재 위치 뿐만 아니라 현재 길이도 같이 저장하자. 현재 위치가 n-1이면 다온거니까 여기에 저장되어 있던 길이를 반환하면 된다. (BFS를 사용했으므로 가장 먼저 조건에 만족된 값이 가장 짧은 값!)(n-1, n-1) 위치에 도착하지 않았는데 더 이상 갈 곳이 없을 수도 있다. bfs 함수 마..

https://leetcode.com/problems/number-of-islands/description/ 문제설명grid가 땅(1)과 물(0)으로 구성되어 있을 때, 섬(물로 둘러싸져 있고 땅으로 구성된)은 몇 개 만들 수 있는지 ?  문제해결grid 전체를 탐색해봐야 하는데 하나로 연결되어 있지 않을 수 있으니까 전체적인 visit 필요만약 방문하지 않았고 해당 값이 “1”이면 -> bfs/dfs 실행 -> 끝나면 +1개class Solution: def numIslands(self, grid: List[List[str]]) -> int: def dfs(cur_r, cur_c): visit[cur_r][cur_c] = True dr = [0,..

https://leetcode.com/problems/coin-change/description/ 1. 문제설명coins에 들어있는 coin을 이용해서 amount 만들 때, 필요한 최소 개수만들 수 없으면 -1를 반환하고 각 coin의 개수는 무한개로 가정 2. 문제해결최소 개수를 구하는 거니까 BFS 이용단, 그냥 BFS로 구현하면 메모리 초과 에러 발생가지를 뻗기 전에 cur_v와 coin을 더한 값을 방문했는지 visit을 통해 확인class Solution: def coinChange(self, coins: List[int], amount: int) -> int: from collections import deque def bfs(): q = d..

https://leetcode.com/problems/is-graph-bipartite/ 1. 문제설명주어진 그래프가 Bipartite인지 아닌지 반환 2. 문제이해하나의 노드가 A라면 엣지로 연결된 노드들이 모두 B이어야 한다.만약 하나의 노드가 B로 저장되어 있고, 이와 연결된 노드도 B로 저장되어 있으면 Bipartite 불가 3-1. 문제해결 (BFS)만약 next_v가 방문처리 되어 있지 않을 경우 connect 확인 connect에 저장되어 있지 않을 경우 : 반대로 저장 (A-B)connect에 저장되어 있을 경우 : 반대로 되어 있는지 확인 (똑같으면 False 반환) 그래프의 노드들이 모두 하나로 연결되어 있지 않고, 여러개의 그래프가 나올 수도 있으니까 전체적인 visit을 만들어서 방..