Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
Tags
- 우선순위큐
- 엘라스틱서치
- 다이나믹프로그래밍
- 시뮬레이션
- 01BFS
- 이젠 골드구현도 어렵네..
- 다익스트라
- COSPROJAVA1급
- 백준
- PS
- 자바PS
- 게더타운시작
- 백준코딩테스트
- spring
- BFS
- java
- 재귀함수
- 네트워크플로우
- deque
- 취득후기
- 구현
- 알고리즘
- dp
- 완전탐색
- COSPRO
- DFS
- GatherTown
- YBMCOS
- QUICKSTARTGUIDE
- 세그먼트트리
Archives
- Today
- Total
공부공간
BOJ - 14502) 연구소 본문
벽 3개를 세워 바이러스가 퍼지지 않은 안전 구역을 최대화해야 하는 문제로, BFS 및 재귀 함수의 사용이 필요하다. 문제 해결의 기본 개념은, 재귀 함수를 이용하여 0 으로 표시된 모든 부분에 대하여 벽을 세우는 것을 고려하고, BFS 를 통하여 바이러스가 퍼진 후의 데이터에서 안전영역의 수를 도출하여 지속적으로 비교하는 것이다.
기존의 입력값, 임의의 벽을 세운후의 새로운 배열, 벽을 세운 배열에서 바이러스가 퍼지고 난 다음의 배열의 총 3가지 배열이 사용되어야 한다.
BFS 개념을 사용하기 위하여 큐를 선언한다. 벽이 세워진 후 복제된 배열인 replica 의 정보를 바이러스가 퍼진후의 데이터를 도출하기 위해 spread 행렬에 대입하고, queue 에 바이러스의 위치를 넣는다. 이후, BFS 의 기본 형태에 따라 큐가 완전히 비워질 때 까지 while 문을 반복하여 바이러스가 퍼진후의 배열을 도출하고, 이후 안전영역의 개수를 구하고 max 함수를 사용하여 최고값을 갱신한다.
재귀함수를 사용하여, 복제 배열 내부에 벽이 3개 세워질 때 까지 함수를 반복하고 벽이 3개 세워졌다면 BFS 함수를 실행시킨다.
'알고리즘 > 완전탐색(BFS,DFS)' 카테고리의 다른 글
BOJ- 2573 ) 빙산 (0) | 2019.12.14 |
---|---|
BOJ - 2583) 영역 구하기 (0) | 2019.12.14 |
BOJ - 2468) 안전 영역 (0) | 2019.12.12 |
BOJ -11403) 경로 찾기 (0) | 2019.12.11 |
BOJ - 1012 ) 유기농 배추 (0) | 2019.12.11 |
Comments