프로그래머스. 보행자 천국

tose33 2022. 1. 10. 15:51

코딩테스트 연습 - 보행자 천국

3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2

programmers.co.kr

몇일동안 이문제만 본것같다.

처음에 bfs로 풀었지만 시간초과가 나서 dfs와 dp를 이용해서 풀었는데 상당히 애를 먹었다.

푼 방법은 각 칸에서 오른쪽으로 갔을때와 아래로 갔을때 도착지점에 도달할수 있는 경우의 수를 기록했다.

int mark[dir][r][c]

mark[0][2][3] 이라면, (2,3)에서 오른쪽으로 갔을때 도착지점에 도달할수 있는 경우의 수.

mark[1][2][3]이라면, (2,3)에서 아래로 갔을때 도착지점에 도달할수 있는 경우의 수.

시간초과를 방지하기 위해 처음에 mark 배열을 -1로 초기화 한후

다음 칸으로 이동했을때 범위를 넘었거나 벽이라면 0으로 기록해놓고,

도달한 칸이 -1이 아니라면 리턴하도록 했다. (이미 다른 루트에서 계산이 완료된 칸이기 때문에 더이상 진행할 필요가 없으므로)

다른 분들의 코드를 봤다.

dfs를 안쓰신 분들도 있었고, dfs를 썼는데 내 코드 보다 훨씬 간결한 분들도 있었다.

나는 각 칸에서 오른쪽으로 갔을때와 아래로 갔을때 도착지점에 도달할수 있는 경우의수를 기록했었는데

왼쪽 or 위에서 해당 칸으로 왔을때 도착지점에 도달할수 있는 경우의수를 기록하면 코드가 더 간결해진다.

mark[dir][r][c]

mark[0][2][3] 이라면, 왼쪽칸에서 오른쪽으로 이동해 (2,3)에 왔을때, 도착지점에 도달할수 있는 경우의 수.

dfs를 쓰지않은 bottom-up dp 방식.