[BOJ] 16234번: 인구 이동

 

 

<<한 번 더 보기>>

 

문제 링크

https://www.acmicpc.net/problem/16234

 

 

TIL

• 같은 코드 시간초과에 대해
  
  • while 문을 메인 함수에 그대로 사용하면 시간 초과
  • 함수를 빼서 재귀 or while 함수 따로 빼면 통과
  • 파이썬은 지역변수 접근이 전역 변수 접근보다 훨씬 빠르게 이루어지기 때문
  • 참고
    • https://www.acmicpc.net/board/view/149122
    • https://www.acmicpc.net/board/view/86503
• 추가적으로 이 문제에선 set()을 사용하는 게 조금 더 빨랐음
  • 아무래도 리셋을 많이 해야하고, open된 걸 다시 확인해야했어서 그런듯
• 같은 날에 처리한 것들을 구분하는 방법으로 참고할 만한 코드
  • https://www.acmicpc.net/source/63235749
• 시간 1등 코드 >> 보니까 불필요한 반복 줄이기 + 필요한 만큼만 실행하기 (2000번 for loop) + 함수 세분화
  • https://www.acmicpc.net/source/84683489

[정답은 맞지만 80%에서 시간 초과난 코드] (아마 극단적인 엣지 케이스에서 시간 초과난듯)

n, l, r = map(int, input().split())

grid = []
for _ in range(n):
    grid.append(list(map(int, input().split())))

directions = [(0,1), (1,0), (-1,0), (0,-1)]
open = set()    # [[False for _ in range(n)] for _ in range(n)]
visited = [[False for _ in range(n)] for _ in range(n)]
stack = []

days = 0
while True:
    
    has_move = False
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                stack.append((i,j))
                visited[i][j]=True
                cnt = 0
                while stack:
                    cy, cx = stack.pop()
                    visited[cy][cx] = True

                    for dy, dx in directions:
                        ny, nx = cy+dy, cx+dx
                        if 0<=ny<n and 0<=nx<n and not visited[ny][nx]:
                            if l<=abs(grid[cy][cx]-grid[ny][nx])<=r:
                                stack.append((ny,nx))
                                open.add((ny,nx))
                                open.add((cy,cx))
                                
                                # print(open)
                                # if not open[cy][cx]:
                                #     open[cy][cx]=True
                                #     cnt += 1
                                #     sum += grid[cy][cx]
                                # if not open[ny][nx]:
                                #     open[ny][nx] = True
                                #     cnt+=1
                                #     sum+=grid[ny][nx]
                cnt = len(open)
                # print(open) 
                if cnt != 0 :
                    sum_p = sum(grid[y][x] for y,x in open)
                    # for y, x in open:
                    #     sum += grid[y][x]
                    total = sum_p//cnt
                    # print(f"total: {total}")
                    for y, x in open:
                        grid[y][x] = total
                        visited[y][x]=True
                    has_move = True
                    open = set()
    # print(has_move)
    if has_move:
        days += 1
    else:
        break
        # [[False for _ in range(n)] for _ in range(n)]
    visited = [[False for _ in range(n)] for _ in range(n)]
    # print(grid)

print(days)

 

 

 

code

• 재귀로 푼 코드 (시간 통과) + recursion limit 설정 필요

 

n, l, r = map(int, input().split())

grid = []
for _ in range(n):
    grid.append(list(map(int, input().split())))

directions = [(0,1), (1,0), (-1,0), (0,-1)]
open = set()    # [[False for _ in range(n)] for _ in range(n)]
visited = [[False for _ in range(n)] for _ in range(n)]

def dfs(coord):
    cy, cx = coord[0], coord[1]
    visited[cy][cx] = True

    cnt = 1
    for dy, dx in directions:
        ny, nx = cy+dy, cx+dx
        if 0<=ny<n and 0<=nx<n and not visited[ny][nx] and (ny,nx) not in open:
            if l<=abs(grid[cy][cx]-grid[ny][nx])<=r:
                open.add((ny,nx))
                open.add((cy,cx))
                cnt += dfs((ny,nx))
    return cnt
    
days = 0
while True:
    has_move = False
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                cnt = dfs((i,j))
                if cnt > 1 :
                    sum_p = sum(grid[y][x] for y,x in open)
                    total = sum_p//cnt

                    for y, x in open:
                        grid[y][x] = total
                        visited[y][x]=True
                    has_move = True
                    open = set()

    if has_move:
        days += 1
    else: break

    visited = [[False for _ in range(n)] for _ in range(n)]

print(days)

 

• stack으로 푼 코드 (시간 통과)

n, l, r = map(int, input().split())

grid = []
for _ in range(n):
    grid.append(list(map(int, input().split())))

directions = [(0,1), (1,0), (-1,0), (0,-1)]
open =  set() 
visited = [[False for _ in range(n)] for _ in range(n)]
stack = []

def dfs(coord):
    i, j = coord[0], coord[1]
    global open
    global visited
    global stack

    has_move = False
    if not visited[i][j]:
        stack.append((i,j))
        visited[i][j]=True

        while stack:
            cy, cx = stack.pop()
            visited[cy][cx] = True

            for dy, dx in directions:
                ny, nx = cy+dy, cx+dx
                if 0<=ny<n and 0<=nx<n and not visited[ny][nx] and (ny,nx) not in open:
                    if l<=abs(grid[cy][cx]-grid[ny][nx])<=r:
                        stack.append((ny,nx))
                        open.add((ny,nx))
                        open.add((cy,cx))
        
        cnt = len(open)
        if cnt != 0 :
            sum_p = sum(grid[y][x] for y,x in open)
            total = sum_p//cnt

            for y, x in open:
                grid[y][x] = total
                visited[y][x]=True

            has_move = True
            open = set()
    return has_move

days = 0
while True:
    days_add = False
    for i in range(n):
        for j in range(n):
            if dfs((i,j)):
                days_add = True

    if days_add:
        days += 1
    else:
        break
    visited = [[False for _ in range(n)] for _ in range(n)]

print(days)

 

• dfs로 연합이 된 땅을 체크 > open()에 set()으로 추가
• 같은 날에도 dfs가 여러 번 실행될 수 있으니 주의해야함 !!!
  • 그러기 위해 중첩 for문을 만들어 하루에 무조건 전체 grid를 방문하게 함
  • 방문 시, days_add 를 체크해서 true면 for loop을 전부 다 순회하고 +1하도록 처리
• 위와 같은 방법도 가능하지만 days 배열을 만들어서 처리하는 게 더 깔끔한 코드 같음 (위에 참고에 있음)
  • day 1, day 2 이런식으로 체크해서 같은 데이면 +1이 안되도록 설정