목록모두 즐거운 시간되기를 (1)

kakasoo

[DFS] 테트로미노 (백준 14500번)

숫자가 예쁜 문제다, 14500번. 일단 문제에 대해서 간단한 해설을 쓰자면, 이건 무조건 dfs로밖에 풀 수 없는 문제다. 간단히 문제를 요약하건대, 아무 숫자가 적혀져 있는 2차원 배열이 주어질 때, 그 배열 위에 테트로미노 (이상, 위에 나와 있는 5가지 도형, 그리고 그 도형의 회전과 대칭)를 올려서 테트로미노 위에 적혀져 있는 숫자들의 합이 가장 큰 것을 구하는 문제이다. 고로 테트로미노가 4칸을 합쳐서 만든 도형이라는 특성 상, dfs든 bfs든 4칸이 되는 순간, 합을 반환하고 종료시켜야 하는데, bfs는 한 지점으로부터 상하좌우로 이동하기 때문에, 만들어진 도형이 반드시 인접할 거란 보장이 없다. 그에 반해 dfs는 한붓그리기와 같은 형태라서 안심하고 사용할 수 있다. 다만 dfs의 경우에..
프로그래밍/알고리즘 풀이 2020. 3. 3. 23:13
이전 Prev 1 Next 다음