[Python] 백준 17070. 파이프 옮기기 1

https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

이전에 풀었던 '등굣길' 형태의 길찾기 문제의 심화 버전 느낌이었다.

[Python] 프로그래머스. 등굣길 (Level 3)

좌표평면에서 해당 좌표까지 도착하는 방법의 개수를 구하면 되는데, 좌표에 도달하는 방법의 개수가 3개라는 차이점이 있다.

 

따라서 가로로 도착하는 경우 / 세로로 도착하는 경우 / 대각선으로 도착하는 경우 세 가지로 나눠서 생각해야 하며,

[y좌표][x좌표][도착하는 방법] 3차원 리스트로 만들어 해결했다.

 

현재 좌표를 x, y라고 하면

 

가로 모양의 현재 좌표 = 가로 모양 (x-1, y) 좌표까지 이동한 방법 + 대각선 모양 (x-1, y) 좌표까지 이동한 방법

세로 모양의 현재 좌표 = 세로 모양 (x, y-1) 좌표까지 이동한 방법 + 대각선 모양 (x, y-1) 좌표까지 이동한 방법

이 된다.

 

대각선은 가로 -> 대각선, 세로 -> 대각선, 대각선 -> 대각선 세 가지 형태가 있으므로

대각선 모양의 현재 좌표 = 가로 모양 (x-1, y-1) 좌표까지 이동한 방법 + 대각선 모양 (x-1, y-1) 좌표까지 이동한 방법 + 세로 모양 (x-1, y-1) 좌표까지 이동한 방법이 된다.

 

 

	import sys
	n = int(sys.stdin.readline())
	maps = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
	# 가로, 세로, 대각선의 idx를 각각 0, 1, 2로 설정.
	table = [[[0]*3 for _ in range(n)] for _ in range(n)]
	# 파이프의 오른쪽 끝만 도착하면 되기 때문에, 파이프 오른쪽을 기준으로 설정
	table[0][1][0] = 1
	# 첫 위치에서 가로로만 이동하는 방법의 개수
	for x in range(2, n):
	if maps[0][x] == 0:
	table[0][x][0] = table[0][x-1][0]
	# 이동하기
	for y in range(n):
	# x는 idx 1에서부터 출발하고, x가 idx 1로 되돌아가는 방법은 없다.
	# 가로 -> 대각선 -> 세로를 최소한 한 번은 거쳐야 하기 때문
	for x in range(2, n):
	# 가로, 세로, 대각선 어디에서든 대각선으로 머리를 변경할 수 있다.
	# 대각선으로 이동할 수 있는 경우
	if maps[y][x] == maps[y][x-1] == maps[y-1][x] == 0:
	table[y][x][2] = table[y-1][x-1][0] + table[y-1][x-1][1] + table[y-1][x-1][2]
	# 다음 칸으로 움직일 수 있는 경우
	if maps[y][x] == 0:
	# 가로로 이동하는 경우 = 대각선 -> 가로, 가로 -> 가로
	table[y][x][0] = table[y][x-1][2] + table[y][x-1][0]
	# 세로로 움직이는 경우 = 대각선 -> 세로, 세로 -> 세로
	table[y][x][1] = table[y-1][x][2] + table[y-1][x][1]
	print(sum(table[-1][-1]))

view raw [백준] 파이프 옮기기 1.py hosted with ❤ by GitHub