DFS(2)
-
[백준] 16198 | 에너지 모으기 | C++
풀이의 핵심은 이렇다. 0. 입력받은 에너지값들(배열 inp)을 마음껏 조작할 수 있도록 객체 하나를 복사생성해둔다(배열 cpy). 1. DFS는 처리해야 할 구슬의 순서(배열 ord)를 작성한다. 2. 순서구성이 완료되면: 계산할 에너지합 변수 선언(tmp = 0) 구슬처리(cpy조작) 위한 순서탐색(for ord): 해당순서(ord[i])의 에너지값을 사용했단 의미에서 0을 대입(cpy[ord[i]]=0) 해당순서의 이전순서(ord[i]-1)를 l, 다음순서(ord[i]+1)를 r로 선언 사용되지 않은(0이 아닌) 구슬을 찾기 위해 l, r 세팅 세팅완료된 l, r을 이용하여 tmp에 에너지 모은다. 모아둔 tmp가 res보다 크다면 res 갱신 3. 최댓값 res를 출력 0. 구슬을 사용하면 그 구..
2022.09.03 -
[백준] 2583 | 영역 구하기 | C++
풀이 전에, 선을 기준으로 한 좌표체계를 공간으로 바꾸는 방법은 의외로 간단하다. 오른쪽 위 꼭지점 좌표를 end포인터처럼 생각하면 된다. (소스코드의 input함수 참고) 그러면 아래 그림의 좌표체계를 선이 아닌, 공간처럼 인식할 수 있다. 1. DFS 풀이 DFS 풀이의 핵심은 이렇다. int 영역넓이(전역변수); 풀이함수(solution)에서 좌표마다 반복: 만약 빈 좌표라면: DFS를 돌린다(빈 좌표갯수 count, 인접한 빈 좌표들을 채운다); 반환값1(영역갯수)++; 영역넓이를 반환값2에 저장한다; 영역넓이를 0으로 초기화한다; void DFS(좌표): 현재 좌표를 채운다; 영역넓이++; 4방향반복: 만약 togo좌표가 비어있다면: DFS(togo좌표) 재귀진입; 각 영역마다의 넓이를 전역변수..
2022.07.15