 사과개발자의 일상

안녕하세요! daily_D 입니다! 👩🏻‍💻 오늘은 DFS 와 BFS의 원리와 이를 코드로 작성하는 방법에 대해서 써볼까합니다! DFS 와 BFS, 알고리즘하면 거의 가장 먼저 배우게 되는 것들이죠! 아마 알고리즘 원리는 몰라도 이름은 들어보신 분들이 많을거에요! 그래서 DFS, BFS 가 뭐냐! 하면!! DFS는 Depth-First-Search의 약어로 깊이 우선 탐색이고 BFS 는 Breadth-First-Search 의 약어로 너비 우선 탐색입니다. 이 둘은 그래프를 탐색하는 방법들입니다! 그럼 그래프가 뭐냐.. 하면 그래프는 정점(node)들과 이 정점들을 연결하는 간선(edge)으로 이루어진 자료구조를 말합니다. 그래프 탐색은 하나의 정점을 시작으로 다른 정점들을 모두 한번씩 방문하는 것을 말..

🍋 문제링크 https://www.acmicpc.net/problem/17086 🍎 코드 제출 기록 (메모리 및 시간) 메모리 : 135476 KB 시간 : 1008 ms 🥝 메모 nx = x + dx[i] *1, ny = y + dy[i] *1nx = x + dx[i] *2, ny = y + dy[i] *2 이런 식으로 완전탐색을 수행하면 아래의 그림과 같이 ✔️ 부분이 확인되지 않기때문에 틀림! nx = x + dx[i] *2, ny = y + dy[i] *2 🍉 Code import copy N, M = map(int, input().split()) shark = [] for i in range(N): shark.append(list(map(int, input().split()))) dx = [-1..

🍋 문제링크 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 🍎 코드 제출 기록 (메모리 및 시간) 메모리 : 135476 KB 시간 : 132 ms 🥝 메모 nx = x + dx[i] *1, ny = y + dy[i] *1nx = x + dx[i] *2, ny = y + dy[i] *2 이런 식으로 완전탐색을 수행하면 아래의 그림과 같이 ✔️ 부분이 확인되지 않기때문에 틀림! nx = x + dx[i] *2, ny = y + dy[i] *2 🍉 Code #include #inclu..

🍋 문제링크 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 🍓 문제풀이 해당 문제는 BFS와 visited 를 사용해서 풀었습니다. 일단은, 매개변수로 들어오는 results 는 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 으로 보기 쉽지 않게 저장되어있기 때문에 아래와 같이 i 가 j 를 이겼다면 win의 의미로 arr[i][j] = 'w' i 가 j 에게 졌다면 lose 의 의미로 arr[i][j] = 'l' 아무 승패관계가 없는 칸은 nothing의 의미로 arr[i][j] = 'n'으로 2차원 배열 새롭게 저장하였습니다. 그 후 arr[i][j] 를 돌면서 각 칸이 자기 자신과의..

🍋 문제링크 https://www.acmicpc.net/problem/1260 🍎 코드 제출 기록 (메모리 및 시간) 메모리 : 3656 KB 시간 : 4 ms 🍉 Code #include #include #include int N; int M; int V; std::vector arr[1001]; std::queue bfs_arr[1001]; std::queue dfs_arr[1001]; std::queue bfs_result; int visited[1001] = {0 , }; void input_faster() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); } void my_queue_sort(int i) { s..