이차원배열

[python3] 백준 9465 풀이 ( 스티커, 다이나믹 프로그래밍, 이차원 배열 )

문제를 쓱 읽어 보면 DP의 냄새가 솔솔솔~ 난다. 딱 봐도 그리디로 풀 수 없고 완전 탐색을 진행해야만 풀 수 있는 상황이다. 그렇다면 역시 DP로 풀어야한다. DP로 풀기 위해서는 다음 단계에 영향을 미쳐야 한다. 즉, 선택한 스티커의 상하좌우에 위치한 다른 스티커를 선택할 수 없다. 우선 dp를 이차원배열이라 한다. 또한 dp에는 각 행별로 열까지의 최댓값을 가진다. 따라서 천천히 생각해보자 만약 0열의 i를 뽑을 것이라면 0열의 dp[0][i-1]을 뽑을 수 없다. 따라서 0열이 아닌 1열의 i-1까지인 dp[1][i-1]을 더할 수 있다. 그러면 식은 dp[0][i] = dp[1][i-1] 이다. 또한 한가지를 더 생각해 보아야 한다. i-1의 열의 스티커의 값이 형편 없다면 이걸 무시하고 i-..

백준 2206 파이썬 풀이 (BFS, 벽 부수고 이동하기, 이차 배열 사용)

이 문제는 정말 나를 못살게 괴롭히는 놈이었다. 배열을 어떻게 해야할지 어떤 기준으로 visited를 하게 할지 굉장히 고민을 많이 하게 만들었다. 3차원 배열로 풀으라는데 내 방식대로 풀기 위해 상당히 고생을 했다. 우선 경우를 나누어본다. 벽을 뿌수고 이동하는 경우에는 다양하게 길이 갈리게 된다. 따라서 이미 누군가 지나간 길에 대해서 계속 갈지 말지를 정해야한다. 편의상 플레이어(경로를 가는 포인트)와 스킬(벽을 부쉈는지 아닌지)이라고 하겠다. 그렇다면 4가지 경우로 나눈다. 1. 스킬을 쓰지 않은 플레이어가 지나간 자리를 스킬을 쓰지 않은 플레이어가 마주쳤을때 => 더이상 진행할 이유가 없다. 왜냐면 앞선 플레이어가 더 효율적 2. 스킬을 쓰지 않은 플레이어가 지나간 자리를 스킬을 쓴 플레이어가 ..