hyeoneee's blog

BFS를 연습해보기 위해서 

이 문제를 풀어보았다.

main에서는 먼저 데이터를 map에 넣어주고

가장 중요한 것은 

해당단지마다 bfs를 돌려준다는 것이다...

한번에 bfs를 돌려서 전체 탐색을 하는 것이 아니라

단지마다 bfs를 돌려서

해당 단지에 집이 몇가구 있는지를

세어야 하기 때문이다.

그리고 몇단지인지도 세어야 하기때문에 

사실 bfs를 처음 호출되는 횟수만큼이

단지 수라고 볼 수 있겠다.

queue에 데이터를 관리하기 쉽게 pos에

정점 y와x를 선언해서

class를 선언해주었다.

그리고 가장 중요한

bfs method

먼저 queue에 값을 넣어주고

queue가 빌때까지

while문을 돌려준다.

그리고 d 배열 

그니깐 아래,위,오른쪽,왼쪽으로 

이동할 좌표를 입력해놓은 배열을

for를 돌면서

새로운 좌표를 구해준다

그게 newY, newX

구한 새로운 좌표값을 먼저

1. 경계값을 체크해준다.

( 0보다 큰지, N 보다 작은지)

2. 그리고 단지에 포함되는지를 체크한다

map[newY][newX] == 1

3. 그리고 방문한 적이 있는지? 도 체크해준다

visited[newY][newX] == fasle

해당 조건들이 모두 통과가 되었으면

queue에 들어갈 자격이 된닷!!

그렇다면 

queue에 값을 넣어주고 

방문했다고 체크해주고

그리고 단지내 가구수의 count 를 늘려준닷

그리고 해당 queue가 비면

(단지내 가구를 모두 방문했으면)

해당 단지내 가구수 가 나왔기 때문에

정답인 ArrayList에 count 배열을 넣어준다.

그리고 맨마지막에 출력할때에는

ArrayList의 수가 총 단지의 수이고

각 count가 단지내 가구 수가 된다.

그래서 ArrayList를 라이브러리를 

이용해 정렬해주고

출력해주면된다~~

DFS와 BFS 문제이당

츄욱,,,,,

대학교때 다 했던건데,,,

지나면 까먹는닷 ^^,,,

그래도 교수님이 잘 설명해주셔서

엄청!! 잘이해했다

(지금만큼은,,,)

여기선 하나만 더하면된다

기본적인 DFS와 BFS를 하고

오름차순 순으로 출력하라고 했으니깐

인접리스트에 오름차순으로 넣어주면 된당!!!!

츄욱,,,

이거때문에 선생님한테 물어도 봣당^_^,,,,,

BFS는

큐를 사용하였고

DFS는 스택을 사용하였당

그리고 DFS는 재귀를 사용!

그리고 C배열을 이용하여

방문하였는지 안하였는지를 쳌쳌!!!!