반응형
1. 풀이
풀이 방법은 아래와 같다.
(1) 백조끼리 만날 수 있는지 확인
(2) 물에 닿는 빙판을 물로 녹이기
(3) 시간+=1
처음에 했던 단순한 풀이는 (1)을 항상 1번백조에서 2번백조로 bfs를 통해서 확인하고, (2)를 처음부터 끝까지 2중포문으로 돌면서 상하좌우에 물이 닿아있는것을 체크해준 뒤, 반복문이 끝나고 한꺼번에 녹여주는 방법을 썼다. 하지만 이것은 시간초과를 발생시켰다.
해결방법은 이전까지 확인해준 영역을 저장해 두었다가 다음 반복에서 생략해 주는 것이다.
즉 (1)에서는 1번백조에서 bfs를 통해 뻗어 나갈 수 있는 최대한으로 뻗어나가서 테두리를 저장해두고 해당 테두리만 q에 넣어서 다음반복에서 bfs를 돈다. 방문했던 곳은 다시 방문하지 않기위해 swanVisited리스트로 이를 관리한다.
(2)에서도 마찬가지로 현재 테두리로 저장되어있는 곳을 녹이고, 다음 반복에서 녹을 빙판(물과 닿아있는)을 q에 넣는다. 이 역시 방문했던 곳은 다시 방문하지 않기 위해 meltVisited리스트로 관리한다.
2. 소스코드
(1) 시간초과
from collections import deque
dR=[0,0,-1,1]
dC=[1,-1,0,0]
R,C=map(int,input().split())
L=[]
bird=[]
for i in range(R):
temp=list(input())
if "L" in temp:
bird.extend([i,temp.index("L")])
L.append(temp)
r1,c1,r2,c2=bird
#백조 도달가능?
def isPossible():
visited=[[-1 for j in range(C)] for i in range(R)]
q = deque([[r1, c1]])
visited[r1][c1]=1
while(q):
r,c=q.popleft()
for k in range(4):
tempR=r+dR[k]
tempC=c+dC[k]
if 0<=tempR<R and 0<=tempC<C and visited[tempR][tempC]==-1 :
if L[tempR][tempC]==".":
q.append([tempR,tempC])
visited[tempR][tempC]=1
elif L[tempR][tempC]=="L":
return True
return False
#얼음 녹기
def melt():
toMelt=[[0 for j in range(C)] for i in range(R)] #녹을부분은 1로
#녹일빙하 찾기
for i in range(R):
for j in range(C):
if L[i][j]=="X":
#한군데라고 물닿으면 녹임
for k in range(4):
tempI=i+dR[k]
tempJ=j+dC[k]
if 0<=tempI<R and 0<=tempJ<C and L[tempI][tempJ]==".":
toMelt[i][j]=1
break
#녹이기
for i in range(R):
for j in range(C):
if toMelt[i][j]:
L[i][j]="."
day=0
while(1):
if isPossible():
print(day)
break
else:
#물녹기시작
melt()
day+=1
'''
for i in L:
print(i)
'''
(2) 통과
from collections import deque
import sys
dR=[0,0,-1,1]
dC=[1,-1,0,0]
R,C=map(int,input().split())
L=[]
bird=[]
for i in range(R):
temp=list(input())
if "L" in temp:
bird.extend([i,temp.index("L")])
L.append(temp)
r1,c1,r2,c2=bird
#백조 도달가능?
def isPossible(q):
global swanQ
nextSwanQ=[]
while(q):
r,c=q.popleft()
for k in range(4):
tempR=r+dR[k]
tempC=c+dC[k]
if 0<=tempR<R and 0<=tempC<C and swanVisited[tempR][tempC]==-1:
if L[tempR][tempC]==".":
q.append([tempR,tempC])
swanVisited[tempR][tempC]=1
elif L[tempR][tempC]=="X":
nextSwanQ.append([tempR,tempC])
swanVisited[tempR][tempC]=1
else:
return True
swanQ=deque(nextSwanQ)
return False
#얼음 녹기
def melt(q):
global meltQ
nextMeltQ=[]
#녹이기
for r,c in q:
L[r][c]="."
#다음 녹일거 찾기
while(q):
r,c=q.popleft()
for k in range(4):
tempR=r+dR[k]
tempC=c+dC[k]
if 0<=tempR<R and 0<=tempC<C and meltVisited[tempR][tempC]==-1:
if L[tempR][tempC]=="X":
meltVisited[tempR][tempC]=1
nextMeltQ.append([tempR,tempC])
else:
meltVisited[tempR][tempC]=1
q.append([tempR,tempC])
meltQ=deque(nextMeltQ)
day=0
#백조변수
swanQ=deque([[r1,c1]])
swanVisited=[[-1 for j in range(C)] for i in range(R)]
swanVisited[r1][c1]=1
#빙하녹이기 변수
meltQ=deque([])
meltVisited=[[-1 for j in range(C)] for i in range(R)]
for i in range(R): #초기화
for j in range(C):
if L[i][j]!="X" and meltVisited[i][j]==-1:
meltVisited[i][j]=1
q=deque([[i,j]])
while(q):
r,c=q.popleft()
for k in range(4):
tempR=r+dR[k]
tempC=c+dC[k]
if 0<=tempR<R and 0<=tempC<C and meltVisited[tempR][tempC]==-1:
if L[tempR][tempC]=="X":
meltQ.append([tempR,tempC])
meltVisited[tempR][tempC]=1
else:
q.append([tempR, tempC])
meltVisited[tempR][tempC] = 1
while(1):
'''
for i in L:
print(i)
print()
'''
if isPossible(swanQ):
print(day)
break
else:
#물녹기시작
melt(meltQ)
day+=1
반응형