[파이썬] 백준 1577 : 도로의 개수 (골드5)

[파이썬] 백준 1577 : 도로의 개수 (골드5)

1577번: 도로의 개수

---

문제

---

풀이

 

0. 방향성 생각

• 웰노운 문제
• 최단거리로 이동하니까 왼쪽위에서 시작해서 항상 아래, 오른쪽 방향으로만 간다.
• 왼쪽과 위쪽 테두리를 채워준 후, 어떤 지점의 왼쪽, 위쪽에서 들어오는 간선이 공사중이 아니면 값을 더해준다.

1. 입력

import sys
input = lambda : sys.stdin.readline().rstrip()

w,h = map(int,input().split())

danger = set()
for _ in range(int(input())):
    a,b,c,d = tuple(map(int,input().split()))
    danger.add((a,b,c,d))
    danger.add((c,d,a,b))

• 헷갈리니까 그냥 간선정보 순서 상관없이 두 개 저장한다

 

2. 출력

arr = [[0]*(w+1) for _ in range(h+1)]
arr[0][0] = 1

for x in range(w):
    if (x,0,x+1,0) not in danger: arr[0][x+1] = 1
    else: break

for y in range(h):
    if (0,y,0,y+1) not in danger: arr[y+1][0] = 1
    else: break

for y in range(1,h+1):
    for x in range(1,w+1):
        if (x,y,x-1,y) not in danger: arr[y][x] += arr[y][x-1]
        if (x,y,x,y-1) not in danger: arr[y][x] += arr[y-1][x]

print(arr[-1][-1])

• 배열 정보 업데이트
• 테두리 부분은 항상 1가지 방법으로 밖에 못간다. (도로가 막혀있지 않은 경우에)
• 특정 노드로 들어오는 도로가 안막혀있으면 값을 더해주기

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

w,h = map(int,input().split())

danger = set()
for _ in range(int(input())):
    a,b,c,d = tuple(map(int,input().split()))
    danger.add((a,b,c,d))
    danger.add((c,d,a,b))

arr = [[0]*(w+1) for _ in range(h+1)]
arr[0][0] = 1

for x in range(w):
    if (x,0,x+1,0) not in danger: arr[0][x+1] = 1
    else: break

for y in range(h):
    if (0,y,0,y+1) not in danger: arr[y+1][0] = 1
    else: break

for y in range(1,h+1):
    for x in range(1,w+1):
        if (x,y,x-1,y) not in danger: arr[y][x] += arr[y][x-1]
        if (x,y,x,y-1) not in danger: arr[y][x] += arr[y-1][x]

print(arr[-1][-1])

 

코멘트

프로그래머스에서 비슷한 문제 본듯? 웰노운