[백준] 인구이동 | 삼성

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

 

1. 문제 이해 및 해결과정

*처음 생각 -상하좌우 VISITED 배열 -차이 계산한 것을 둘 TMP배열   1. 차이를 계산한다.   2. 차이 값이 범위 밖이면 벽을 두어 막는다.      차이 값이 범위 이내인 것이 하나도 없다면 종료   3. 인접한 것끼리 BFS 하여 인구 계산   4. 다시 1번으로 돌아감   -어떻게 차이 값을 계산한 배열을 둘 것인가? -국경선을 어떻게 둘 것인가?  => 벽을 둔다고 생각하지 말고 범위내에 있으면 같은 숫자로 visited함(방문한 위치에 연합된 것을 알기 위해 index로 체크하하는 것)  -BFS의 조건이 범위차이 내에에 있는가 임  - 모든 나라의 위치에서 DFS,BFS를 수행하여 인접한 나라의 인구수를 확인한 뒤에, 가능하다면 국경선을 열고 인구 이동 처리를 진행하면 된다 => 연합체크 하나 하고 데이터 바꾸는 것이 아니라 모든연합 체크 후 갱신

반례 

4 1 9
96 93 74 30
60 90 65 96
5 27 17 98
10 41 46 20
답: 1

 

5 1 5
88 27 34 84 9
40 91 11 30 81
2 88 65 26 75
75 66 16 14 28
89 10 5 30 75
답: 1

 

2. 풀이방법

 1. BFS

#인구 이동
#https://www.acmicpc.net/problem/16234
import sys
from collections import deque
sys.stdin = open("input.txt","r")
n,l,r=list(map(int,input().split()))
arr=[]
for _ in range(n):
    arr.append(list(map(int,input().split())))

dh=[-1,1,0,0]
dw=[0,0,-1,1]

res=0 #결과

#연합하여 인구 이동
def union(united,sum,cnt):
    for i,j in united:
        arr[i][j]=sum//cnt

#특정 위치에서 출발하여 모든 연합을 체크한 뒤에 데이터 갱신
def bfs(h,w,index):
    #(h,w)와 연결된 나라 정보를 담는 리스트
    united=[]
    united.append((h,w))
    q=deque() #bfs를 위한 큐
    q.append((h,w))
    visited[h][w]=index #현재 연합 번호 할당, visited체크
    sum=arr[h][w] #현재 연합의 인구 수
    cnt=1 #현재 연합 국가 수
    while q:
        cur = q.popleft()
        for i in range(4):
            nh = dh[i] + cur[0]
            nw = dw[i] + cur[1]
            if 0 <= nh < n and 0 <= nw < n and visited[nh][nw] == -1:#아직방문하지 않은 곳은 -1
                if l <= abs(arr[nh][nw] - arr[cur[0]][cur[1]]) <= r:
                    q.append((nh, nw))
                    visited[nh][nw] = index
                    sum += arr[nh][nw]
                    cnt += 1
                    united.append((nh,nw)) #연결되어 있는 것을 저장, pop하는 과정이 없음
    union(united,sum,cnt)

while True:
    visited = [[-1] * (n) for _ in range(n)]  # 방문 초기화(방문하지 않았으면 -1)
    index=0
    for i in range(n):
        for j in range(n):
            cnt = 0  # 첫시작
            sum = 0
            if visited[i][j]==-1: #아직 방문하지 않았으면
                bfs(i,j,index)
                index+=1
    #인구 이동이 모두 끝나면
    if index == n*n:
        break
    res+=1

print(res)

 

3. 오답원인

  1. 오답풀이 

 

#인구 이동 - 틀린코드
#https://www.acmicpc.net/problem/16234
import sys
from collections import deque
sys.stdin = open("input.txt","r")
n,l,r=list(map(int,input().split()))
arr=[]
visited = [[False] * (n) for _ in range(n)] #방문 초기화
dh=[-1,1,0,0]
dw=[0,0,-1,1]
for _ in range(n):
    arr.append(list(map(int,input().split())))

def bfs(i,j):
    global cnt,sum
    q=deque()
    q.append((i,j))
    visited[i][j]=True
    sum=arr[i][j]
    cnt=1
    while q:
        cur = q.popleft()
        for i in range(4):
            nh=dh[i]+cur[0]
            nw=dw[i]+cur[1]
            if 0<=nh<n and 0<=nw<n and visited[nh][nw]==False:
                if l<=abs(arr[nh][nw]-arr[cur[0]][cur[1]])<=r:
                    q.append((nh,nw))
                    visited[nh][nw]=True
                    sum+=arr[nh][nw]
                    cnt+=1
                    #print("cnt:",cnt)

def union():
    for i in range(n):
        for j in range(n):
            if visited[i][j]==True:
                arr[i][j]=sum//cnt

res=0
one=0
for i in range(n):
    for j in range(n):
        cnt = 0  # 첫시작
        sum = 0
        if visited[i][j]==False:
            bfs(i,j)
        if cnt == 0:
            break
        if cnt==1:
            one+=1
        print(sum,cnt,sum//cnt)
        union()
        res += 1

if one==n*n:
    res=0
print(res)

2. 오답

import sys
from collections import deque
sys.stdin = open("input.txt","r")
n,l,r=list(map(int,input().split()))
arr=[]
visited = [[False] * (n) for _ in range(n)] #방문 초기화
dh=[-1,1,0,0]
dw=[0,0,-1,1]
flag=False
for _ in range(n):
    arr.append(list(map(int,input().split())))

def bfs(i,j):
    global cnt,sum,flag,ans
    q=deque()
    q.append((i,j))
    visited[i][j]=True
    sum=arr[i][j]
    cnt=1
    while q:
        cur = q.popleft()
        for i in range(4):
            nh=dh[i]+cur[0]
            nw=dw[i]+cur[1]
            if 0<=nh<n and 0<=nw<n and visited[nh][nw]==False:
                if l<=abs(arr[nh][nw]-arr[cur[0]][cur[1]])<=r:
                    q.append((nh,nw))
                    visited[nh][nw]=True
                    sum+=arr[nh][nw]
                    cnt+=1
                    flag=True
                    #print("cnt:",cnt)
    if cnt!=1:
        union()

def union():
    for i in range(n):
        for j in range(n):
            if visited[i][j]==True:
                arr[i][j]=sum//cnt

res=0
one=0
while True:

    flag = False  # 인구이동이 일어나지 않음
    visited = [[False] * (n) for _ in range(n)]  # 방문 초기화
    for i in range(n):
        for j in range(n):
            cnt = 0  # 첫시작
            sum = 0
            if visited[i][j]==False:
                bfs(i,j)
            if cnt == 0:
                break
            if cnt==1:
                one+=1
            # if cnt!=1:
            #     union()


    if flag==False:
        break
    else:
        res += 1

print(res)

- 정답 코드와의 차이점

 1) visited배열에 True/False 로만 구분한 것이 아니라 연합 된 곳별로 index를 둠 (union[h][w]=index)

 2) 현재 위치와 연결된 나라 정보를 담는 리스트 united를 둠 

 

4. 알게된 점

- BFS 큐 이외에 다른 연결정보를 담는 다는 생각을 해보는 것

- 방문표시를 T/F 외에 index로 하는 것  

for문에서 여러 변수를 한 번에 꺼낼 수 있음

def union(united,sum,cnt):
    for i,j in united:
        arr[i][j]=sum//cnt