챌린징 포인트:
1. 큐에 무엇을 담을지 정해야함 >> 방문한 것만 담기
2. 1에 따른 큐에 담을 조건을 설정(how)
상태설정
0 : 미방문
1 : 미방문 && 불은 켠 상태
2 : 방문 (불을 켜야만 방문 가능하므로 불도 on)
root(1,1과 연결되었는 그룹) 명명.
-이슈
1. 기존에 불만 켜놓았다가 연결되어 있지 않다가 방문한 것이 다리가 되어서 방문했던 것의 벡터까지 root가 되는 경우를 고려해야함
2. 연산을 줄이기 위해 매번 1,1에서 O(n^2)을 할 수는 없다. 총 최종적으로 n^3이 되어버림
3. 2의 이슈에 의해 불을 켜면서도 root와의 연결을 판단 할 수 있어야 한다.
4. 불의 벡터중에 root가 있다면 이번엔 불 켠 것이 다리가 되기 때문에 그것 또한 방문해야한다.
[기존 알고리즘-how]
1. pop후 light벡터를 무조건 켠다 이 때 상태값이 1로.
2. 큐에서 팝한 것의 벡터 중 미방문 && 불만 켜져있는 경우 그 벡터를 담음
3. 불 켠것을 순회 - 이때 '불켠것의 벡터'(2번과 다름) 중 그룹화되어있는게 있다면 '불켠것'(벡터아님)을 큐에 담음
[시간 초과 이유]
1번에서 불을 그냥 무조건 켜게되면 이미 방문되어있던 걸 큐에 넣을 필요가 없고 값 또한 바꿀 필요가 없었는데 바꾸어 버려서
계속 순환하게된다. 값변경도 이루어지므로 초반 케이스는 운좋게 시간초과가 나온것이고 알고리즘 자체도 틀린게 된다.
[수정 후]
기존 알고리즘 1에서 light벡터를 무지성으로 1로 변경하던 것 >>> 미방문시에만 1로 변경으로 수정.
구현
import sys
from collections import deque
n, m = input().split()
n = int(n)
m = int(m)
light = [[[]for _ in range(n+1)] for __ in range(n+1)]
origin = [[0]*(n+1) for ___ in range(n+1)]
for _ in range(m):
y,x,a,b = map(int,sys.stdin.readline().strip().split())
light[y][x].append([a,b])
def BFS():
q = deque()
q.append((1,1))
origin[1][1] = 2
while(q):
y,x = q.pop()
#fire
for ll in light[y][x]:
if origin[ll[0]][ll[1]] < 2:
origin[ll[0]][ll[1]] = 1
###
### vector check
ny = [1,0,-1,0]
nx = [0,1,0,-1]
for o in range(4):
dy = ny[o] + y
dx = nx[o] + x
if dx > n or dy > n or dx < 1 or dy < 1:
continue
if origin[dy][dx] == 1:
origin[dy][dx] = 2
q.appendleft((dy,dx))
###
###light check
for lll in light[y][x]:
if origin[lll[0]][lll[1]] == 2:
continue
nny = [1,0,-1,0]
nnx = [0,1,0,-1]
for ii in range(4):
dy = nny[ii] + lll[0]
dx = nnx[ii] + lll[1]
if dx > n or dy > n or dx < 1 or dy < 1:
continue
if origin[dy][dx] == 2:
origin[lll[0]][lll[1]] = 2
q.appendleft((lll[0], lll[1]))
BFS()
cnt = 0
for i in range(n+1):
for j in range(n+1):
if origin[i][j]:
cnt+=1
print(cnt)