BFS

[python] 백준 - 3055. 탈출

🤔문제 해결 G5 | BFS, 그래프? 단순히 최단거리를 찾는 것과 달리 맵이 계속 변하는 문제이다. 로직은 간단하다. 고슴도치를 상하좌우로 이동시킨다. 물도 상하좌우로 흘러넘친다. 다시 고슴도치를 상하좌우로 이동시킨다. (하지만 물에 잠겨있는 고슴도치는 이동할 수 없다) 다시 물을 상하좌우로 흘러넘치게한다. 위의 과정을 반복하면서 고슴도치가 굴에 도착하면 끝 💨 💻소스 코드 def flood(w): new_water = [] for x, y in w: for k in range(len(dx)): nx = x + dx[k] ny = y + dy[k] if 0

[python] 백준 - 16953. A → B

🤔문제 해결 S1 | 그래프, BFS 난 DFS 알고리즘 분류에는 그래프와 BFS로 나와있는데 잘 모르겠고, DFS로 해결했다. 목표 숫자부터 두가지 경우로 나눠서 들어간다. 맨 끝의 숫자가 1이면 1을 버리고 재귀 맨 끝의 숫자가 1이 아닐 때 2로 나누어 떨어지면 2로 나누고 재귀 테스트 케이스 3번을 예시로 하겠다 ( 100, 40021 ) 40021: 맨 끝의 숫자가 1이므로 1을 버린다 40021 => 4002 체크하는 방법은 10으로 나눈 나머지, 버리는 방법은 10으로 나눈 몫 4002: 맨 끝의 숫자가 1이 아니고 2로 나누어 떨어지므로 2로 나눈다. 4002 => 2001 2001: 버린다. 2001 => 200 200: 나눈다. 200 => 100 100: 100 == A 이므로 그만!..

[python] 백준 - 1926. 그림

🤔문제 해결 S1 | BFS, 그래프 그림을 하나 선택 한다. 그 그림의 상하좌우를 탐색한다. 만약 상하좌우에 그림이 있다면 그 그림을 선택 후 다시 상하좌우 선택한다. 더 이상 처음 선택한 그림과 연결된 그림이 없을 때 까지 탐색. 위의 과정을 반복한다. 처음 그림을 선택하면 그림의 갯수 +1 그림선택후 상하좌우 탐색하면서 그림을 찾으면 그림의 크기 +1 💨 기본적인 BFS 문제 💻소스 코드 from collections import deque def bfs(x, y): q = deque() q.append((x, y)) images[i][j] = 0 size = 1 # 최초 들어갈 때 그림 크기 1로 시작 while q: x, y = q.popleft() for k in range(4): # 상하좌우..

[python] 백준 - 1743. 음식물 피하기

🤔문제 해결 S1 | BFS 이번에는 2차원리스트를 활용하지 않고 set()을 활용하여 문제를 해결했다. 각각의 좌표가 주어져 있으므로 쓰레기를 하나 선택해 상하좌우 BFS탐색을 한다. 주변의 쓰레기를 선택할 때마다 visited 에 add 해준다. 또 count + 1 을 해줘서 쓰레기 더미의 크기를 answer 에 담는다. 💨 set() 을 쓰는 이유 if tmp in set() : 이렇게 tmp가 set()에 있는지 없는지 확인할 때 시간복잡도가 O(1) 이다. 하지만 if tmp in list : list의 경우 O(n) 이다. 💻소스 코드 import sys from collections import deque def bfs(x, y): q = deque() q.append((x, y)) cnt..

[python] 프로그래머스 - 블록 이동하기(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 1. Lv3 | BFS 심화 2. BFS를 돌릴 q와 방문체크할 visited리스트를 준비한다. (1) q는 deque를 이용. 로봇의 좌표 4가지 (x1,y1,x2,y2)와 현재의 거리 d 를 넣는다. (2) visited에는 로봇의 좌표만 넣는다. 3. BFS를 돌린다. (1) 먼저 끝점에 도달했다면 바로 멈춰주고 거리를 출력한다. (2) 그렇지 않다면 로봇이 세로인경우와 가로인경우를 나누고, 상하좌우 움직일 수 있는 지 체크한다. (3) 로봇이 세로인 경우 오른쪽 이동이 가능하면 오른쪽 회전도 가능하다. 마찬가지로 왼쪽이동이 가능하면 왼쪽으로 회전도 가능하다. (4) 가로도 마찬가지 (5) 이동이나 회전이 가능하면 visited리스트를 확인해 방문한적이 없으면 q와 visited에 넣어..

[python] SWEA - 1238. [S/W 문제해결 기본] 10일차 - Contact

🤔문제 해결 1. D4 | BFS 2. 주어진 인풋값으로 인접리스트를 만든다. 3. 똑같은 노드를 탐색하는 것을 막기 위해 방문여부를 확인할 visited 리스트, BFS에서 같은 깊이에서 가장 큰 숫자를 기억해둘 result를 만들고 deque를 이용해 BFS 탐색을 한다. 4. 재귀 함수를 이용해서 BFS의 깊이마다 result의 값을 갱신해준다. 5. 마지막으로 갱신된 result 를 출력 💨 💻소스 코드 from _collections import deque def contact(current_q): global result # 마지막 연락받은 사람들 중 가장 큰 값 result = max(current_q) # 다음 연락 받을 사람들이 들어갈 리스트 next_q = deque() # 현재 연락받..