Q21. 인구이동

16234번: 인구 이동 (acmicpc.net)

16234번: 인구 이동

 

전형적인 탐색 문제다.

탐색인데 약간 시뮬레이션을 곁들인..?

 

1. 모든 나라에 대해서 탐색을 수행한다. 이미 방문한 나라는 탐색 ㄴㄴ.

2. 탐색할 때에는 국경을 열 국가를 모두 찾고 이미 방문했다고 체크해둔다. 국경이 열린 국가를 하나의 set로 만들어서 저장해둔다.

3. 탐색이 다 끝나면 국경이 열린 국가들끼리 인구이동을 실시한다.

4. 국경을 한 번이라도 열었으면 day count를 1 증가시키고 아니면 day count를 출력하고 프로그램을 종료한다.

 

대충 요런 흐름으로 만들 예정이다.

 

N, L, R = map(int, input().split())
grid = [[A for A in map(int,input().split())] for _ in range(N)]

newgrid = [[99999] * (N+2) for _ in range(N+2)]

for i in range(N):
    for j in range(N):
        newgrid[i+1][j+1] = grid[i][j]

def search(grid,r,c,visited):
    global L,R

    dx = [0,0,-1,1]
    dy = [1,-1,0,0]

    visited.add((r,c))

    for i in range(4):
        newr = r + dx[i]
        newc = c + dy[i]

        diff = abs(grid[r][c]-grid[newr][newc])
        if (newr,newc) not in visited and diff >= L and diff <= R:
            search(grid,newr,newc,visited)

def avg_visited(grid,visited):
    _sum = 0
    for r,c in visited:
        _sum += grid[r][c]
    avg = _sum//len(visited)
    for r,c in visited:
        grid[r][c] = avg

daycount = 0
while True:

    total_visited = set()
    visited_list = []
    for i in range(N):
        for j in range(N):
            if (i+1,j+1) in total_visited:
                continue
            visited = set()
            search(newgrid,i+1,j+1,visited)
            visited_list.append(visited)
            total_visited = total_visited | visited

    for visited in visited_list:
        avg_visited(newgrid,visited)


    if len(visited_list) != N*N:
        daycount += 1
    else:
        break

print(daycount)

 

정확도는 문제가 없는데 시간초과가 떴다.. 맙소사 ㅠ

문제는 방문 체크하는 부분이었다. 첨엔 total_visited를 set로 만들어서 체크했는데 이게 같은 O(1)이어도 2차원 리스트를 만들어서 방문체크를 하는 방법보다 확실히 더 연산이 비싼모양이다.

 

N, L, R = map(int, input().split())
grid = [[A for A in map(int,input().split())] for _ in range(N)]

newgrid = [[99999] * (N+2) for _ in range(N+2)]

for i in range(N):
    for j in range(N):
        newgrid[i+1][j+1] = grid[i][j]

def search(grid,r,c,visited,total_visited):
    global L,R

    dx = [0,0,-1,1]
    dy = [1,-1,0,0]

    sum = grid[r][c]

    visited.add((r,c))
    total_visited[r][c] = False

    for i in range(4):
        newr = r + dx[i]
        newc = c + dy[i]

        diff = abs(grid[r][c]-grid[newr][newc])
        if total_visited[newr][newc] and diff >= L and diff <= R:
            sum += search(grid,newr,newc,visited,total_visited)

    return sum

def avg_visited(grid,visited,avg):
    for r,c in visited:
        grid[r][c] = avg

daycount = 0
while True:

    moved = False
    total_visited = [[True] * (N+2) for _ in range(N+2)]
    for i in range(N):
        for j in range(N):
            if total_visited[i+1][j+1]==False:
                continue
            visited = set()
            sum = search(newgrid,i+1,j+1,visited,total_visited)
            if len(visited) > 1:
                moved = True
            avg_visited(newgrid,visited,sum//len(visited))

    if moved:
        daycount += 1
    else:
        break

print(daycount)