본문 바로가기

BFS4

(백준) 2667번: 단지번호붙이기 파이썬 풀이(BFS&DFS) 1. 문제풀러가기 2. 문제 해결 코드 3. 로직 분석 1. 문제풀러가기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 해석: - 1로 이어진 부분을 체크하고, 이어진 부분의 개수 출력하기 2. 문제 해결 코드 코드 (성공) DFS풀이 import sys input = sys.stdin.readline n = int(input()) v = [[False for _ in range(n)] for _ in range(n)] #방문체크 리스트 .. 2022. 11. 27.
(백준) 18352번: 특정 거리의 도시 찾기 - 파이썬 풀이 (BFS, 그래프) 1. 문제풀러가기 2. 문제 해결 코드 3. 로직 분석 1. 문제풀러가기 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 문제 요약: - X(시작지점)도시 부터 K만큼 이동해서 갈 수 있는 도시 출력. - 중요포인트 : 오름차순 정렬! 예) N=4, M=4, K=2, X=1일 때 도시는 1~4까지 있음 => N=4 주어진 도로의 개수는 4개 => M=4 최단 거리가 2 이.. 2022. 11. 23.
코딩테스트 준비 - 프로그래머스: 게임 맵 최단거리 풀이/BFS (파이썬) 프로그래머스: 게임 맵 최단거리 풀이 포스팅 요약 1. 프로그래머스 풀이 2. BFS에 관한 포스팅 링크 3. DFS,BFS 코딩문제 링크 문제풀러가기 https://programmers.co.kr/learn/courses/30/lessons/1844?language=python3 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 풀이 1. 위,아래,오른쪽,왼쪽 방향으로 전진하며, 이미 지나간 곳은 체크를 하는 형식으로 dfs혹은 bfs 탐색이다. 2. 최.. 2021. 6. 28.
(알고리즘)BFS(Breadth-First-Search) 너비 우선 탐색 - 파이썬 + 백준 2178 풀이 BFS 1. BFS동작 예시 - 가까운 노드부터 우선적으로 탐색하는 알고리즘 - BFS는 큐를 사용하여 너비 우선으로 탐색한다. 집어 넣은 순서대로 1 -> 2 -> 3 -> 5 -> 4 -> 8 -> 6 -> 7 2. BFS 코드 예시 from collections import deque #queue를 사용하기 위해 쓰임 리스트를 사용해도 되지만, #deque이 시간을 더 단축해줌. def bfs(graph, start, visited): queue = deque([start]) #처음 정점을 넣어줌 visited[start] = True while queue: v = queue.popleft() print(v, end=' ') # 한 줄로 출력 for i in graph[v]: #만약 v=1일때 i는.. 2021. 6. 10.

티스토리툴바