문제 링크

문제 설명

input

sign_list

각 노드의 4 사이클 신호

Ex)

리스트 3번 인덱스의 신호가 [1,7,6,4]이고 현재 사이클이 4라면

1➡️7➡️6➡️4➡️1

3번 노드의 현재 신호는 1번 신호이다.

output

len(cross)

cross는 자동차가 방문한 노드의 집합이다.
이 길이를 구하면 자동차가 방문한 모든 노드의 개수를 알 수 있다.

algorithm

BFS

특정 노드에서 모든 노드를 방문해야하므로 그래프 탐색 알고리즘을 사용해야 한다. 난 그저 너비 우선 탐색을 택했다.

문제 조건을 자세히 읽어보고 구현하기를 바란다.

설계

1

# BFS
q = deque([(1,0,0,0,0)]) # bx,by,x,y,cycle
cross = set()
while q:
    bx,by,x,y,cycle = q.popleft()
    if cycle > T:
        continue
    cross.add((x,y))
    sign = sign_list[x][y][cycle%4]
    next_list = get_next(sign,bx,by,x,y)

    if next_list:
        for dx,dy in next_list:
            nx = x+dx
            ny = y+dy

            if 0<=nx<N and 0<=ny<N:
                q.append((x,y,nx,ny,cycle+1))

• 이전 노드와 현재 노드의 좌표 / 현재 사이클이 필요하다.
• 현재 사이클이 제한 사이클을 넘어간다면 방문 처리를 하지 않는다.
• 현재 좌표와 사이클을 통해 현재 신호를 알아낸다.
• [현재 신호+이전 좌표+ 현재 좌표]를 통해 [다음 방문지]를 알아낸다.
• [다음 방문지] 중에서 맵 범위를 벗어나지 않는 노드만 방문한다.

2

def get_next(sign,bx,by,x,y):
    if sign == 1 and y-by == 1:
        return [(-1,0),(0,1),(1,0)]
    if sign == 2 and x-bx == -1:
        return [(0,-1),(-1,0),(0,1)]
    if sign == 3 and y-by == -1:
        return [(-1,0),(0,-1),(1,0)]
    if sign == 4 and x-bx == 1:
        return [(0,-1),(1,0),(0,1)]
    if sign == 5 and y-by == 1:
        return [(-1,0),(0,1)]
    if sign == 6 and x-bx == -1:
        return [(0,-1),(-1,0)]
    if sign == 7 and y-by == -1:
        return [(0,-1),(1,0)]
    if sign == 8 and x-bx == 1:
        return [(1,0),(0,1)]
    if sign == 9 and y-by == 1:
        return [(0,1),(1,0)]
    if sign == 10 and x-bx == -1:
        return [(-1,0),(0,1)]
    if sign == 11 and y-by == -1:
        return [(-1,0),(0,-1)]
    if sign == 12 and x-bx == 1:
        return [(0,-1),(1,0)]
    return []

신호를 제작하는 과정에서 제일 애를 먹었다 ... 👼🏻

처음 설계할 때, 이전 노드를 고려하지 않았다. 무슨 말이냐 하면

<신호 1>을 살펴보자. 현재노드로부터 상,우,하로 갈 수 있다.

그러면 교차로 A에서 상 방향은 맵을 벗어나므로 제끼고 우,하로 갈 수 있다.

아니다. 자동차는 하 방향에서 들어오고 있기 때문에 하는 갈 수 없다.

따라서, 신호를 정할 때 이전 노드의 위치까지 같이 고려해주며 이동 위치를 반환해야 한다.

다시 정리를 하면, <신호 1>은 좌에서 들어왔을 때 상,우,하로 갈 수 있다.

교차로 A는 하에서 들어오므로 False를 return 한다.

코드

"""
input: sign_list
output: len(cross)

sign_list,cycle,cur,appointment --> sign 
before,cur,sign ---BFS--> next 
next --> cross_set --> len(cross_set)
"""

import sys
from collections import deque
input = sys.stdin.readline

N,T = map(int,input().split())
sign_list = [[[] for _ in range(N)] for _ in range(N)]
for i in range(N**2):
    x,y = divmod(i,N)
    sign_list[x][y] = list(map(int,input().split()))


def get_next(sign,bx,by,x,y):
    if sign == 1 and y-by == 1:
        return [(-1,0),(0,1),(1,0)]
    if sign == 2 and x-bx == -1:
        return [(0,-1),(-1,0),(0,1)]
    if sign == 3 and y-by == -1:
        return [(-1,0),(0,-1),(1,0)]
    if sign == 4 and x-bx == 1:
        return [(0,-1),(1,0),(0,1)]
    if sign == 5 and y-by == 1:
        return [(-1,0),(0,1)]
    if sign == 6 and x-bx == -1:
        return [(0,-1),(-1,0)]
    if sign == 7 and y-by == -1:
        return [(0,-1),(1,0)]
    if sign == 8 and x-bx == 1:
        return [(1,0),(0,1)]
    if sign == 9 and y-by == 1:
        return [(0,1),(1,0)]
    if sign == 10 and x-bx == -1:
        return [(-1,0),(0,1)]
    if sign == 11 and y-by == -1:
        return [(-1,0),(0,-1)]
    if sign == 12 and x-bx == 1:
        return [(0,-1),(1,0)]
    return []

# BFS
q = deque([(1,0,0,0,0)]) # bx,by,x,y,cycle
cross = set()
while q:
    bx,by,x,y,cycle = q.popleft()
    if cycle > T:
        continue
    cross.add((x,y))
    sign = sign_list[x][y][cycle%4]
    next_list = get_next(sign,bx,by,x,y)

    if next_list:
        for dx,dy in next_list:
            nx = x+dx
            ny = y+dy

            if 0<=nx<N and 0<=ny<N:
                q.append((x,y,nx,ny,cycle+1))
    

print(len(cross))