백준 B17070-파이프 옮기기1 with 파이썬

문제 17070번: 파이프 옮기기 1 문제 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다. 파이프는 매우 무겁기 때문에, 유현이는 파이프를... www.acmicpc.net 풀이 해당 문제는 3차 시도만에 해결한 문제다. 1차 2차 때는 BFS로 접근했지만 70%대에서 계속 시간초과가 발생했다. 아무리 줄여봐도 시간 초과를 해결할 수 없다고 판단하여서, 다른 접근 방식을 고민해봤고 그 결과 DP를 생각했다. DP 풀이 방식은 코드에 주석으로 자세하게 적어...

원문링크 : 백준 B17070-파이프 옮기기1 with 파이썬