인구이동 (bfs)

문제는 쉽다고 느꼈으나 정작 풀이시간에 꽤 많은 시간을 잡아먹었습니다.

 

저에게 구현 문제의 문제점은, 좀 쉬운 문제가 아니면 깔끔하게 풀리지 않고 몇 개의 테스트 케이스에서 꼭

예외결과가 발생하는데, 이럴때보면 구현에 항상 몇가지 잘못들이 있는 걸 발견하고 이걸 수정하는데 디버깅하면서

해결하느라 문제를 푸는데 시간이 제법 걸리는 것 같습니다.

 

오히려 이런 문제들은 공책에 써가며 처음부터 설계를 하고 예외가 생길 경우까지 생각해서 하는게 구현시간이 훨씬 빨라질 수 있을 것 같단 생각이 들었습니다.

 

대표적으로 이번 인구이동도 단순한 bfs를 응용한 문제이지만, 이중포문으로 visited처리를 하다보니 돌아서 연결되는 부분을 디버깅 도중에 발견하다던가, 처음 bfs에 넣을때 생기는 예외 조건들 처리 , 등 구체적인 조건들을 완전히 생각하고 풀거나 적고 고려하고 해야하는데 그냥 쉽구나 빨리 풀어야겠다 하는 생각에 손부터 나가다 보니 꽤 풀이가 (고치느라) 늦어지고 악순환이 반복되는 것 같습니다.

 

다음 세부적인 조건이 필요한 구현부터는 조금 설계를 자세히 고려하고 푸는 습관을 들여야겠습니다.

 

from collections import deque

 

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

board = [[0]*n for _ in range(n)]

ct = [[0]*n for _ in range(n)]

visited = [[0]*n for _ in range(n)]

 

for i in range(n):

    nums = list(map(int,input().split()))

    for j in range(n):

        board[i][j] = nums[j]

 

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

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

 

def bfs(x, y, t):

    global board

    global ct

    q = deque()

    q.append((x,y))

    ct[x][y]=t

 

    totalCt = 1

    totalValues = board[x][y]

 

    while q:

        front = q.popleft()

        cx= front[0]

        cy = front[1]

        

        for i in range(4):

            nx = cx+dx[i]

            ny = cy+dy[i]

            if nx>=0 and nx<n and ny>=0 and ny<n:

                if ct[nx][ny]==0:

                    v = abs(board[cx][cy]-board[nx][ny])

                    # print(l,r)

                    if v>=l and v<=r:

                        ct[cx][cy]=t

                        ct[nx][ny]=t

                        q.append((nx,ny))

                        totalCt+=1

                        totalValues+=board[nx][ny]

    

    return totalCt, totalValues

 

answer = 0

con = False

 

while 1:

    if con:

        break

    totalTest = 0

    

    for a in range(n):

        for b in range(n):

            ct[a][b]=0

        

    t= 1

    for i in range(n):

        for j in range(n):

            if ct[i][j]==0:

                for k in range(4):

                    nx = i+dx[k]

                    ny = j+dy[k]

                    if nx>=0 and nx<n and ny>=0 and ny<n:

                        if ct[nx][ny] == 0:

                            v = abs(board[nx][ny]-board[i][j])

                            if v>=l and v<=r:

                                # print("i,j",i,j)

                                tc, tv = bfs(i,j,t)

                                

                                # print("tc,tv", tc,tv)

                                re = tv//tc

                        

                                # for a in range(n):

                                #     print(ct[a])

                                # print()

                                

                                for a in range(n):

                                    for b in range(n):

                                        if ct[a][b]==t:

                                            board[a][b]=re

                                t+=1

 

                                # for a in range(n):

                                #     print(board[a])

                                # print()

                                

                                if tc>=2:

                                    totalTest+=1

                                break

    # print("totalTest",totalTest)

 

    if totalTest ==0:

        con = True

    else:

        answer+=1

print(answer)