bfs의 대체적인 로직구조

핵심 자료구조(Core data structure)

• 2차원 배열(int[][]): 맵이나 그래프를 나타낸다. 배열안의 값은 방문 여부를 나타내는 경우가 많다.
• 방문 여부 판단 배열(boolean[][]): 같은 2차원 배열이다. 무한 루프와 필요없는 과정을 생략하기 위해 방문 여부를 표기한다.

핵심 로직(Key Logic)

다른 모든 이웃한 이웃 셀을 자동으로 방문하면서 작동한다. 큐를 사용함으로써 작동한다.

1. 초기화

• queue생성 (Queue<int[]>)
• 2D boolean 배열 선언과 false로 무두 초기화
• 첫번째 방문 지점 (x,y)를 queue에 넣는다.
• 방문표시를 한다. visited[x][y] = true

2. 탐색 loop(보통 while문 )

bfs알고리즘의 핵심은 while문이다. 큐가 빌 때까지 아래의 로직을 반복하면 된다.

• 가장 앞의 큐 원소를 빼낸다.
• 방문가능한 모든 이웃한 셀들을 체크한다. (left,right, up, down)
• 각 이웃한 셀들에 대해 (nx,ny) , 다음 조건을 확인한다.
  - 경계안에 있는가?
  • 갈 수 있는 곳인가?
  • 방문하지 않은 곳인가?
• 만약 위의 모든 조건을 충족한다면:
  - 방문처리를 한다.
  • 큐에 인접한 셀을 넣는다. (nx,ny)