어제 드래곤커브 실패하고 슬펐지만....
SKT 코테도 보고 이것도 봤다...
SKT코테 솔직히 다 구현에 완전탐색으로밖에 안보였고 고생했고 결과는 좋지 않지만... 노력하겠다.
이문제는 솔직히 골드5인데 까다롭다... 문제만 쫌 오래 본거 같다.
요약하자면 게이트를 열고 다 더해서 그 수만큼으로 나눈게 분배인데 분배가 안될때까지 하는거다.
DFS BFS 둘중에 하나 쓰면 될꺼같은데... 요즘 BFS코딩이 훨씬 익숙해서 덜 익숙한 DFS 연습좀 해볼까 했다...
일단 문제를 다 풀고 치명적인 실수로 뻘짓을 한다...
그건 최대 제귀 값을 설정 안했더니 런타임에러가 뜬다는거....
애꿎은것만 엄청 고치고 계속 제출해서 내 정확도만 낮아졌다ㅠ
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
n,l,r = map(int,input().split())
matrix = [list(map(int,input().split())) for _ in range(n)]
def dfs(x,y):
visit.add((x,y))
for a,b in [[0,1],[1,0],[-1,0],[0,-1]]:
xa,yb = x+a,y+b
if 0<=xa<n and 0<=yb<n and l <= abs(matrix[xa][yb]-matrix[x][y]) <=r and (xa,yb) not in visit and (xa,yb) not in full:
dfs(xa,yb)
full = {1}
ans = 0
while full:
full = set()
for i in range(n):
for j in range(n):
if (i,j) not in full:
visit = set()
dfs(i,j)
mx = 0
if len(visit) > 1:
for a,b in visit:
mx += matrix[a][b]
mx //= len(visit)
for a,b in visit:
matrix[a][b] = int(mx)
full.update(visit)
if full:
ans += 1
print(ans)그래도 내 풀이는 결론은 시간초과다...
풀다보니 깨달은것은 dfs를 한번 시행할때 visit이 들고 또한 그렇게 인구이동을 한 위치는 while문을 다시 돌기 전까지 절대 시행하면 안된다...
이거때문에 평소 set을 가지고 시행 여부를 판단했었는데 set을 두개를 써서 고생을 한다...
좌표를 검색할때 set안에서 검색하는게 시간초과의 주 원인인거 같다..
다른 블로그를 찾다 dfs로 짠거를 봤는데
난 전체 확인은 full이란 set과 각각 dfs마다 확인은 visit으로 했는데
확인한 코드는 전체를 visit 이차원 리스트와 단일 리스트에 append하는 식으로 dfs한 좌표들을 저장했다.
이렇게 해야 나중에 그 리스트로 for 문 돌리거나 length를 계산할 수 있어서 편한거 같다ㅠ
암튼 저렇게 짰어야하는데... 어렵다어려워
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
n,l,r = map(int,input().split())
matrix = [list(map(int,input().split())) for _ in range(n)]
def dfs(x,y):
visit[x][y] = True
for a,b in [[0,1],[1,0],[-1,0],[0,-1]]:
xa,yb = x+a,y+b
if 0<=xa<n and 0<=yb<n and l <= abs(matrix[xa][yb]-matrix[x][y]) <=r and not visit[xa][yb]:
loca.append((xa,yb))
dfs(xa,yb)
return loca
full = {1}
ans = 0
while True:
visit = [[False]*n for _ in range(n)]
flag = False
for i in range(n):
for j in range(n):
loca = [(i,j)]
if not visit[i][j]:
loca = dfs(i,j)
if len(loca)>1:
flag = True
sum = 0
for x,y in loca:
sum+=matrix[x][y]
avg = sum//len(loca)
for x,y in loca:
matrix[x][y] = int(avg)
if not flag:
print(ans)
break
ans+=1물론 이 문제는 BFS가 훨씬 쉬울꺼같고 고생한거 같긴한데...
암튼 전체적인 방법론은 나랑 똑같은데 visit으로 좌표를 확인하는 방법에 set대신 리스트를 활용한 방법들을 앞으로 고민해봐야겠다.
이렇게 했을 때 훨씬 시간적으로 빠르다... 좌표를 찍어서 확인하라고 주니까 좌표만 가지고 전체에서 있는지 없는지보다 훨씬 빠를 수 밖에 없는 거 같다.
더 열심히 해야겠다..
