본문 바로가기
728x90

코딩테스트/DFS\BFS6

[python] 백준 1012번: 유기농 배추 #bfs 실행 for i in range(n): #바깥리스트 for j in range(m): #내부리스트 if graph[i][j] == 1: bfs(i,j) cnt += 1 # cnt = bfs(i,j) print(cnt) https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 위의 문제는 전형적인 bfs/dfs 문제이다. 그러나 최근에 이와 같은 전형을 풀어보지 않아서 개념을 까먹은 상태였다. 그래서 관련 개념을 한번 짚고 문제를 풀려고 한다. DFS는 깊이.. 2023. 1. 29.
<PART 3> Q16.백준 14502번: 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net - pypy3 제출(python3 제출시 시간 초과) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70.. 2022. 11. 16.
<PART 3> Q15.백준 18352번: 특정 거리의 도시 찾기 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 - input.txt파일 만들었을 때 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 from .. 2022. 11. 16.
<PART 2> DFS/BFS 예제 음료수 얼려먹기 N X M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 입력예시) 5 5 10101 00110 10101 01101 11111 출력예시) 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #크기 입력받기 n,m = map(int,input().split()) #2차원 리스트의 맵 정보 입력 받기 graph =[] for i in range(n): graph.append(list(map(int,input()))) count = 0 #dfs 정의 def.. 2022. 11. 5.
<PART 2> DFS/BFS - DFS (Depth-First Search, 깊이 우선 탐색) 그래프에서 깊은 부분을 우선적을 탐색하는 알고리즘입니다. 즉 최대한 멀리있는 노드부터 탐색하는 방법입니다. 여기서 그래프를 표현하는 방법이 2가지가 있습니다. 1. 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식 2. 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식 대략적으로 설명하면 ex) (0) | 7 |5 (1) (2) 형태의 그래프가 존재한다고 가정합니다. 노드 0 1 2 0 0 7 5 1 7 0 무한 2 5 무한 0 인접행렬은 2차원 배열로 각 노드가 연결된 형태로 기록하는 방식입니다, 연결되지 않았을 경우는 무한의 비용이라고 작성합니다. ex) INF = 999999999 #무한의 비용 선언 graph .. 2022. 11. 5.
<PART2> 스택/큐/재귀함수 탐색: 많은양의 데이터 중에서 원하는 데이터를 찾는 과정 대표 탐색 알고리즘인 DFS/BFS를 이해하려면 기본 자료구조인 스택,큐,재귀 함수에 대한 이해가 전제되어야 합니다. 자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성됩니다. -삽입(push): 데이터를 삽입한다. -삭제(pop): 데이터를 삭제한다. push를 할 때는 오버플로우, pop을 할 때는 언더플로우를 조심해야합니다. - 스택 (Stack) 선입후출 또는 후입선출의 구조이다. LIFO(Last in First Out)라고도 한다. 파이썬 코드로 표현하면 다음과 같다. append와 pop자체가 서로 맨 뒤쪽 데이터를 push,pop하는 것이기 때문에 스택은 별도.. 2022. 11. 4.
728x90

티스토리툴바