DFS

1. 개요 안녕하세요. "1103번 게임" 문제의 유형은 dfs를 응용한 다이나믹 프로그래밍입니다. dfs는 재귀로 구현하는 방법과 스택을 사용한 반복문 풀이가 존재합니다. 마찬가지로 다이나믹 프로그래밍도 재귀 + 메모이제이션을 사용한 top-down approach와 반복문을 사용한 bottom-up approach가 존재하죠. 둘 다 재귀로 구현이 가능하다는 공통점이 있기도 해서 그런지 이 둘을 합쳐 응용한 문제를 종종 마주치긴 합니다. 원래 저는 bottom-up 풀이 위주의 다이나믹 프로그래밍 풀이를 하다가 dfs와 응용되는 문제를 좀 더 쉽게 접근하기 위해서 top-down 풀이법을 연습했었습니다. 개인적으로 다이나믹 프로그래밍의 구현 난이도가 bottom-up에 비해 top-down이 더 쉽기..

1. 문제 풀이dfs를 응용한 flood fill 문제였습니다. 배열 어느 곳에서든 시작 위치로 지정하고 탐색을 시도하게 되면 이미 방문한 배열을 재방문하게 됩니다. 재방문하는 한 곳은 두 가지 경우로 볼 수 있습니다. 이전 탐색에서 방문했던 곳이거나 현재 탐색에서 방문했던 곳입니다. 두 가지 경우든 상관없이 재방문했었던 곳의 방문 배열 값으로 다시 돌아가면서 모두 채워주면 됩니다. 이전 탐색에서 방문 했던 곳의 방문 배열 값으로 채웠다는 것은 기존에 있던 그룹에 속하게 되는 것입니다.현재 탐색에서 방문 했던 곳의 방문 배열 값으로 채웠다는 것은 새로운 그룹이 생성된 것입니다. 이런 두 가지 경우를 판단하여 dfs로 flood fill을 하게 되면 문제없이 풀이가 가능합니다. 2. 코드#include u..