해리의 데브로그

(삼성 SW 기출) 백준 16234 - 인구 이동

31 Aug 2019 | Algorithm 백준 삼성 역테 기출

문제

  • [삼성 SW 역량 테스트 기출 문제] 백준 16234 - 인구 이동
  • 문제링크

나의 코드

  • 하루(반복문 전체 탐색)를 기준으로 인구이동 횟수를 계산해야 하는데, 연합이 발생할 때마다 인구이동 횟수를 카운팅하는 방식으로 코드를 처음 짰었다.
  • 이 방법으로 나머지 샘플 TC는 괜찮았는데, 4번째 TC 결과값이 3이 아닌 4가 계속 나와 디버깅을 하다보니 생각보다 많은 시간이 허비되었다. 결국은 코드를 다 엎고 다시 작성하였음.
  • union_lst에는 각 연합에 대한 배열(union_sub_lst)들을 저장시켰으며, union_sub_lst에는 연합에 소속되는 좌표값을 저장시켰음.
  • MyMap 내 정보 업데이트는 전체 탐색이 끝난 후에 일괄적으로 진행하였음.
  • 연합이 발생하지 않을 경우 visited 배열내 값을 -1으로 저장시켜으며, visited 배열이 전부 -1인 경우에 while 문 break 조건을 걸었음.
  • while문이 한번 돌 때마다 cnt값을 1씩 증가시켰다!
#종료 조건
def Check():
    global N
    for y in range(N):
        for x in range(N):
            # visited 배열에 -1이 아닌 값이 있는경우는 False 반환
            if visited[y][x] != -1: return False
    #visited 배열이 전부 -1인경우, True 반환
    return True

def IsSafe(y,x):
    return 0<=y<N and 0<=x<N


def BFS(init_y, init_x):
    global L, R

    Q = []
    #연합을 넣을 배열 선언
    union_sub_lst = []
    visited[init_y][init_x] = 1
    Q.append([init_y, init_x])
    union_sub_lst.append([init_y, init_x])

    while Q:
        y, x = Q.pop(0)
        for dir in range(4):
            n_y = y + dy[dir]
            n_x = x + dx[dir]
            #맵을 벗어나지않고, 연합 조건을 만족시키며, 방문하지 않은 칸인 경우
            if IsSafe(n_y, n_x) and L <= abs(MyMap[y][x] - MyMap[n_y][n_x]) <= R and visited[n_y][n_x] <= 0:
                visited[n_y][n_x] = 1
                Q.append([n_y, n_x]) #Queue에 append
                union_sub_lst.append([n_y, n_x]) #연합 배열에 추가

    # 연합 배열의 길이가 1 => 어디로도 이동하지 못한 경우
    if len(union_sub_lst) == 1:
        visited[init_y][init_x] = -1 #visited를 -1으로 선언
        return
    #그렇지 않은 경우는 전체 연합 배열에 현재의 연합배열을 append
    union_lst.append(union_sub_lst)


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

#상, 하, 좌, 우
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]


cnt = 0
while True:
    visited = [[0] * N for _ in range(N)]
    #연합 "들(복수형)" 을 넣을 배열 선언
    union_lst = []
    for y in range(N):
        for x in range(N):
            if visited[y][x] <= 0:
                BFS(y, x)

    #완탐이 끝난 이후, MyMap 값 업데이트. union_lst 내에는 각 하위 연합에 대한 배열이 존재함
    if union_lst:
        #하위 연합 배열에 대한 반복문
        for i in range(len(union_lst)):
            #하위 연합 길이
            MyLen = len(union_lst[i])
            #하위 연합의 총 합 계산
            MySum = 0
            for j in union_lst[i]:
                MySum += MyMap[j[0]][j[1]]
                visited[j[0]][j[1]] = 1

            #하위 연합별 평균값을 구한 후, MyMap내 값 업데이트
            avg = int(MySum // MyLen)
            for j in union_lst[i]:
                MyMap[j[0]][j[1]] = avg

    #반복문 종료 조건. visited 배열이 전부 -1 인 경우(더이상 연합 생성 불가) while문 종료
    if Check():
        break
    cnt += 1

print(cnt)

Related Posts

Comments