[파이썬] 백준 2151 : 거울설치 (골드3)

[파이썬] 백준 2151 : 거울설치 (골드3)

2151번: 거울 설치

---

문제

---

풀이

 

0. 방향성 생각

• 각 노드가 있는데 들어가는 방향에 따라서 서로 다른 노드로 취급한다.
• visit[y][x][diretion] 으로 설정한다. (n*n*4 크기의 배열이 생성된다)
• 각 노드에 접근할 때, 누적으로 사용한 거울의 개수가 저장된 값보다 작으면 갱신하고 큐에 넣기.
• 큐든 힙이든 둘 다 사용 가능한데 큐가 더 편해서 큐로 진행

1. 입력

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

n = int(input())
arr = [list(input()) for _ in range(n)]

INF = 1e9
visit = [[[INF]*4 for _ in range(n)] for _ in range(n)]

door = []
for i in range(n):
    for j in range(n):
        if arr[i][j] == '#':
            door.append((j,i))

sx,sy = door[0]
ex,ey = door[1]

• 3차원 visit 배열을 만들어준다.
• 시작점을 sx,sy로, 끝점을 ex,ey로 설정한다

2. 탐색

dire = [(1,0),(0,1),(-1,0),(0,-1)]
q = deque()
for i in range(4):
    q.append((sx,sy,i,0))
    visit[sy][sx][i] = 0

while q:
    x,y,d,c = q.popleft()

    for nd in range(4):
        dx,dy = dire[nd]
        nx = x + dx
        ny = y + dy
        if 0<=nx<n and 0<=ny<n and arr[ny][nx] != '*':
            if d%2 == nd%2 and c < visit[ny][nx][nd]:
                visit[ny][nx][nd] = c
                q.append((nx,ny,nd,c))
            if d%2 != nd%2 and arr[y][x] == '!' and c+1 < visit[ny][nx][nd]:
                visit[ny][nx][nd] = c+1
                q.append((nx,ny,nd,c+1))

print(min(visit[ey][ex]))

• d%2 == nd%2 : 현재 방향이랑 이전 방향이 같은 경우, 현재 사용한 거울 수 c가 visit에 저장된 값보다 작으면 갱신
• d%2 != nd%2 : 현재 방향이랑 이전 방향이 다른 경우, 거울 설치가 가능해야한다.
• 이 경우에 c+1이 visit에 저장된 값보다 작으면 갱신한다.
• 도착지점 노드 4가지 중 최소값을 출력

 

---

전체코드

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

n = int(input())
arr = [list(input()) for _ in range(n)]

INF = 1e9
visit = [[[INF]*4 for _ in range(n)] for _ in range(n)]

door = []
for i in range(n):
    for j in range(n):
        if arr[i][j] == '#':
            door.append((j,i))

sx,sy = door[0]
ex,ey = door[1]

dire = [(1,0),(0,1),(-1,0),(0,-1)]
q = deque()
for i in range(4):
    q.append((sx,sy,i,0))
    visit[sy][sx][i] = 0

while q:
    x,y,d,c = q.popleft()

    for nd in range(4):
        dx,dy = dire[nd]
        nx = x + dx
        ny = y + dy
        if 0<=nx<n and 0<=ny<n and arr[ny][nx] != '*':
            if d%2 == nd%2 and c < visit[ny][nx][nd]:
                visit[ny][nx][nd] = c
                q.append((nx,ny,nd,c))
            if d%2 != nd%2 and arr[y][x] == '!' and c+1 < visit[ny][nx][nd]:
                visit[ny][nx][nd] = c+1
                q.append((nx,ny,nd,c+1))

print(min(visit[ey][ex]))

 

코멘트

카카오 경주로 건설, 백준 레이저 통신이랑 비슷한 문제