BFS
-
[프로그래머스] Python - 거리두기 확인하기메모/알고리즘 2022. 5. 10. 20:10
코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 프로그래머스 레벨2 문제로 카카오 인턴십 코딩테스트 출제 문제다. 주어진 리스트에서 사람들이 거리두기를 지키는지 확인하면 된다. 이 문제의 경우 BFS-FloodFill로 해결할 수 있었다. ..
-
[백준] Java - 미로 탐색메모/알고리즘 2022. 4. 27. 23:01
2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 1 9 10 11 12 2 8 12 3 7 13 14 4 5 6 14 15 정말 쉬운 BFS 문제이자 FloodFill 알고리즘을 사용하는 문제이다. 파이썬으로 코테를 준비하다가 자바를 새로 준비해보려니 자바 자체의 문법을 이용하는게 좀 오래 걸렸다. 1, 1의 좌표에서 n, m 좌표까지의 최단 거리를 출력하면 된다. 기본적으로 이동할 수 있는 위치를 표시하는 배열과 방문 여부를 확인하는 배열을 입력 값의 크기만큼 할당하고 시작한다. 위의 표 처럼 다음 이동할 위치에는 현재 위치의 값에 1을 ..
-
[백준] Python - 알파벳메모/알고리즘 2022. 4. 13. 10:41
1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 백준의 그래프 탐색 문제 알파벳이다. 이 문제는 DFS와 BFS 두 가지 방법으로 접근했다. DFS 같은 경우는 재귀를 사용하여 visited 집합에 방문 여부를 저장하는 방식을 사용했다. DFS와 BFS가 모두 인접 행렬/인접 리스트 각각에서 시간 복잡도가 같은 걸로 알고 있는데 DFS 방식은 PyPy3로 해결할 수 있었고 Python3로는 시간초과가 발생했다. BFS를 사용한 방식은 조금의 변형이 있었다. 일반적으로 우리는 FloodFill과 같은 알..
-
[백준] Python - 안전 영역메모/알고리즘 2022. 3. 25. 15:25
2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 음식물 피하기와 마찬가지로 Flood Fill 알고리즘을 알아보고자 푼 문제다. 똑같이 별 다를 건 없고 BFS를 통해 해결했다. 이 문제의 경우 한 가지를 고려해야한다. 바로 강수량이다. 처음에 지역의 높이를 입력하면서 동시에 가장 높은 지역을 확인한다. 가장 높은 지역만큼 비가 온다면 그 높이를 초과하는 강수량은 확인할 필요가 없다. 따라서 비가 안오는 경우인 0부터 가장 높은 높이 -1 까지의 강수량을 가정하고 문제를 푼다. 예를 들어 가장 높은 곳의 높이가 9라..
-
[백준] Python - 음식물 피하기메모/알고리즘 2022. 3. 25. 15:11
1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net FloodFill 알고리즘을 공부해보려고 문제 몇 개를 풀기로 했다. 새로운 알고리즘은 아니고 기존의 DFS/BFS 등을 통해서 풀 수 있는 쉬운 문제였다. 2차원 배열을 생성해서 각 좌표 별 정보를 저장한다. 현재 좌표 기준으로 상하좌우 좌표 중 2차원 배열의 범위 내에 있으면서 음식물이 존재한다면 한 덩어리로 간주하고 Deque에 추가한다. 기존의 BFS를 해결할 수 있는 방법을 통해서 가장 큰 덩어리의 사이즈를 구하..