[Softeer][level3] 안전운전을 도와줄 차세대 지능형 교통시스템 (python)

https://softeer.ai/practice/info.do?idx=1&eid=580 

Softeer

 

문제

 

풀이

BFS문제.

사전에 정의된 교차로 정보 저장하고 하나씩 방문해서 갯수 count

 

처음에 20점이 나오는데 틀린 부분을 찾느라 오래 걸림. 방문했던 곳이어도 다시 방문해도 괜찮았음

import sys
from collections import deque
from pprint import pprint

N, T = map(int, input().split())

intersection = [[0] + [] for i in range(N + 1)]
for i in range(1, N + 1) :
    for j in range(1, N + 1) :
        intersection[i].append(list(map(int, input().split())))

visited = [[0] * (N + 1) for _ in range(N + 1)]

go = [[0, 1], [0, -1], [1, 0], [-1, 0]]   # 동,서,남,북
heading = {                                 # 각 교차로에서 이전 진행 방향
    1:go[0], 2:go[3], 3:go[1], 4:go[2], 
    5:go[0], 6:go[3], 7:go[1], 8:go[2],
    9:go[0], 10:go[3], 11:go[1], 12:go[2]
}
signals = {                                 # 신호 정보
    1:[3,0,2], 2:[1,3,0], 3:[3,1,2], 4:[1,2,0], 
    5:[3,0], 6:[1,3], 7:[1,2], 8:[2,0],
    9:[0,2], 10:[3,0], 11:[3,1], 12:[1,2]
}

def BFS(start) :

    queue = deque()
    queue.append([start, go[3], 0])  # [현재 교차로, 이전에 heading방향, 시간]

    while queue :
        now, prev, t = queue.popleft()
        visited[now[0]][now[1]] = 1
        signal = intersection[now[0]][now[1]][t % 4]

        if prev != heading[signal] :    # 진입 방향과 교차로 진행 방향이 다른 경우
            continue
        move = signals[signal]          # 입력받은 교차로의 신호
        for m in move :                 # 각 신호의 경우
            nx = now[0] + go[m][0]  
            ny = now[1] + go[m][1]
            if nx < 1 or nx > N or ny < 1 or ny > N : # 범위를 벗어나는 경우
                continue
            if not visited[nx][ny] and t+1 <= T :  # 방문하지 않았거나 이동 경로 수보다 작은 경우
                queue.append([[nx,ny], go[m], t + 1])

    tmp = 0
    for i in range(len(visited)) :
        tmp += visited[i].count(1)
        
    return tmp

print(BFS([1,1]))

 

코드

import sys
from collections import deque
from pprint import pprint

N, T = map(int, input().split())

intersection = [[0] + [] for i in range(N + 1)]
for i in range(1, N + 1) :
    for j in range(1, N + 1) :
        intersection[i].append(list(map(int, input().split())))

visited = [[0] * (N + 1) for _ in range(N + 1)]

go = [[0, 1], [0, -1], [1, 0], [-1, 0]]   # 동,서,남,북
heading = {                                 # 각 교차로에서 이전 진행 방향
    1:go[0], 2:go[3], 3:go[1], 4:go[2], 
    5:go[0], 6:go[3], 7:go[1], 8:go[2],
    9:go[0], 10:go[3], 11:go[1], 12:go[2]
}
signals = {                                 # 신호 정보
    1:[3,0,2], 2:[1,3,0], 3:[3,1,2], 4:[1,2,0], 
    5:[3,0], 6:[1,3], 7:[1,2], 8:[2,0],
    9:[0,2], 10:[3,0], 11:[3,1], 12:[1,2]
}

def BFS(start) :

    queue = deque()
    queue.append([start, go[3], 0])  # [현재 교차로, 이전에 heading방향, 시간]

    while queue :
        now, prev, t = queue.popleft()
        visited[now[0]][now[1]] = 1
        signal = intersection[now[0]][now[1]][t % 4]

        if prev != heading[signal] :    # 진입 방향과 교차로 진행 방향이 다른 경우
            continue
        move = signals[signal]          # 입력받은 교차로의 신호
        for m in move :                 # 각 신호의 경우
            nx = now[0] + go[m][0]  
            ny = now[1] + go[m][1]
            if nx < 1 or nx > N or ny < 1 or ny > N : # 범위를 벗어나는 경우
                continue
            if t < T :  # 이동 경로 수보다 작은 경우
                queue.append([[nx,ny], go[m], t + 1])

    tmp = 0
    for i in range(len(visited)) :
        tmp += visited[i].count(1)
        
    return tmp

print(BFS([1,1]))