dfs백준(3)
-
[Python] 🥈 백준 2583 영역구하기 / DFS & BFS 그림 풀이
2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 풀기 전 생각하기 문제 풀기 전 어려웠던 점이 보통 [0,0] 은 왼쪽 위에부터 시작해서 아래로 내려가는 형식인데 아래에서부터 위로 숫자가 커지는 형식이라 그래프를 어떻게 생각해야될지 헷갈렸다.... 그래서 그냥 표를 돌려서 생각했다 그림을 오른쪽으로 돌리면 우리가 평소에 많이 봤던 좌표가 보인다! 그렇다면 다음 문제는 꼭짓점으로만 주어지는 영역을 어떻게 채우냐인데..... 그림을 그려서 꼭짓점과 실제 표의 좌표를 비교해보니 왼쪽 위 꼭..
2024.02.12 -
[Python] 🥈백준 2667 단지 번호붙이기 /DFS를 활용하여 연결요소 구하기
예제 입력 1 7 0110100 0110101 1110101 0000111 0100000 0111110 0111000 예제 출력 1 3 7 8 9 아이디어 생각하기 연결요소 문제는 풀어도 풀어도 뇌리에 안 박혀서 이렇게 블로그를 쓰고자 한다.... 로직순서 변수설명 map: 지도, home: 각각 단지내 집의 수, nums: 각각 단지내 집의 수를 담는 리스트 (1) 단지 지도 생성 (2) dfs 알고리즘을 돌며, ⓐ 범위를 벗어날 때 ⓑ집이 있을 때 ⓒ집이 없을 때 경우를 나눈다. ⓐ ⓒ는 return False (3) ⓑ 집이 있을 때의 경우, home +=1 집을 1개 추가하고 maps[x][y] = 0 #숫자를 세고 0으로 집을 없앰 다시 못 돌게 집을 없애버린다 dfs(x-1,y) #상하좌우 재..
2023.02.19 -
[Python] DFS/BFS 알고리즘 / 백준 1260 그림 풀이 /
개요 그래프에서 노드(정점)와 간선으로 표현된다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 두 노드가 간선으로 연결되어 있다면 인접하다. 라고 표현한다. DFS (깊이 우선 탐색) 그래프에서 깊은 부분을 우선적으로 탐색한다. BFS 알고리즘 (너비우선탐색) 노드에서 갈 수 있는 모든 노드를 다 방문한다. 말 그대로 너비에서 연결된 모든 곳을 일단 큐에 담는다 (1) 시작 노드를 큐에 append한 후 방문처리 (2) 큐에서 노드를 POP, 인접 노드 중 방문하지 않은 노드를 모두 큐에 append (3) 2번 과정을 q가 빌 때까지 반복한다. 주의사항 from collections import deque q= deque([v]) q.popleft() q.pop대신 im..
2023.01.29