BFS

[python] SWEA - 1868. 파핑파핑 지뢰찾기

문제 해결 1. D4 | BFS 2. 클릭이 가능한 부분('.')을 찾아서 클릭을 할지 말지 결정한다 (1) 주변(8방향)에 지뢰가 한개도 없다면 클릭! (2) 하나라도 있으면 건너 뛴다 3. 클릭을 했다면 그 지점의 주변에 지뢰가 아닌부분을 가지고 BFS탐색을 한다. (1) 주변지점을 기준으로 또 그주변에 지뢰가 없으면 계속 퍼져나가면서 탐색한다 (2) 지뢰가 하나라도 있으면 그 지점은 더 나아가지 못한다. 4. 클릭 했을 때 마다 카운트를 세어주고 5. 나머지 클릭이 안된부분을 찾아서 더해주면 끝 💨 처음에 주변에 지뢰가 하나도 없는 지점을 다 찾아놓고 시작하려 했지만 시간이 오래걸릴 거 같아 찾으면서 가는 방식을 선택했다. 다 풀고보니 그렇게 해도 될거같다. 소스 코드 from _collection..

[python] SWEA - 7465. 창용 마을 무리의 개수 / 10200. 구독자 전쟁

1. 창용 마을 무리의 개수 문제 해결 D4 | DFS, BFS, 그래프 1. 주어진 정보로 인접리스트를 만든다. 2. 보통의 그래프 탐색이라면 시작점하나로 BFS나 DFS 탐색을 하고 끝나지만 여기서는 모든 노드를 탐색해야 하므로 3. BFS탐색을 하는 while문을 for문으로 감싸서 모든 노드를 탐색한다. 4. for문을 통해 큐에 들어가는 노드는 한 무리의 시작점이므로 카운트를 세어준다. 🌦 처음 실패는 while 문 안에 for 문을 넣어 시간초과가 났다는 것이다. 여기서 for 문을 바깥으로 꺼내주고 시간초과는 해결, 두번째 실패는 for문을 N까지 돌려서 났다. N+1로 고쳐서 통과했다. 소스 코드 from _collections import deque for tc in range(1, 1 ..

[python] 백준 - 1697. 숨바꼭질

문제 해결 1. BFS 기본 문제. S1 2. 주어진 범위 100,000까지의 배열을 만든다. 3. BFS를 활용해 현재위치와 다음위치를 배열에 넣고 while문을 돌린다 (1) 각 지점에 도달하기 까지의 최소 시간으로 업데이트 해준다. (2) 이렇게 코드를 짜는 경우 시간초과가 생길 수 있으므로 deque()를 사용하고 (3) 한번도 방문한 적이 없거나, 최소시간으로 방문할 때만 다음 지점으로 나아갈 수 있게 한다. 4. 현재 위치가 목표 지점에 도달하면 break로 while문을 빠져나와 답을 출력한다. 🌞 처음에 범위를 100001까지 잡았더니 인덱스가 마지막이 될 경우에 런타임에러가 발생한다. 그래서 100002로 바꿔줬더니 해결했다. 재귀로 풀어 봤지만 maximum recursion depth..

[python] 백준 - 2178. 미로 탐색

문제 해결 1. BFS 기본 문제. S1 2. 출발점을 1로 만들고 한칸씩 전진하며 1씩 더해준다. - BFS 이용 (1) 4 방향 탐색을 위해 dx, dy 를 만든다 ( 상하좌우). (2) 리스트(여기서는 디큐를 사용함)에 출발점을 넣어준다. (3) 탐색이 언제 끝날지 모르니까 while 문을 사용한다. (4) 리스트에서 pop(0)(여기서는 popleft())을 이용해 하나씩 꺼내준다. ( 0번을 꺼내는 이유는 BFS 기법을 사용해야 하기 때문에) (5) 꺼낸 지점에서 4방향 탐색을 해준다. (6) 탐색한 곳(nx, ny)이 '1' 인 경우 그 칸에 현재 칸(x, y) 숫자의 +1을 해주고, 리스트에 append해준다. (7) (4)번부터 다시 반복한다. 3. 각 숫자가 이동한 칸의 갯수를 나타낸다...

[python] 백준 - 4963. 섬의 개수

문제 해결 1. DFS or BFS를 이용해 몇개의 무리가 있는지 알아내는 문제이다. 2. while문 한 싸이클이 돌 떄마다 한무리를 체크할 수 있다. 3. visit배열을 따로 만들어 사용하거나, 지나온 곳을 다른값으로 바꿔주는 방법을 이용한다. 소스 코드 from _collections import deque while True: w, h = map(int, input().split()) if w == 0 and h == 0: break island = [list(map(int, input().split())) for _ in range(h)] # 상 우상 우 우하 하 좌하 좌 좌상 # 8방향 탐색을 위해 dx = [-1, -1, 0, 1, 1, 1, 0, -1] dy = [0, 1, 1, 1, 0..

[python] 백준 - 2606. 바이러스

문제 해결 1. 플로이드와샬 알고리즘 - 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 2. 라고 되어있지만 사실 잘 모르겠고, 이어져있는 정점들을 모두 찾는 문제이다. 3. 인접리스트를 만들고, BFS로 이어져있는 모든 정점을 찾으면 해결되는 간단한 문제! 소스 코드 from _collections import deque def bfs(vertex): # 속도가 빠른 디큐를 사용해서 BFS 탐색 q = deque() q.append(vertex) # 시작점 방문 체크를 True로 해준다음 visit[vertex] = True while q: # 큐에 쌓인 노드들 중에서 하나를 꺼내고 current = q.popleft() # 노드에 인접한 이웃들중 for neighbor in adj[current]..