[백준, 파이썬] 2583번 영역구하기

이 문제는 알고리즘보다는 구현에 조금더 초점이 맞추어진 문제였던것 같습니다. 

사실 알고리즘은 리스트, 큐를 사용하여 인접구간을 탐색하고 조건만 걸어주면 되는 문제라

까다롭지는 않았는데 파이썬 리스트 조작에 익숙하지 않으면 위 그림을 표현하기 애먹을 수 있습니다. 

m,n,k = map(int, input().split(' ')) rect = [] background = [[0 for i in range(n)] for j in range(m)] //일단 0으로 모두 초기화 solve_q = [] result =[] for i in range(k): rect.append(list(map(int,input().split(' ')))) def init(): for i in rect: x1,y1,x2,y2 = i[0],i[1],i[2],i[3] //입력받은 rect값을 기반으로 1을 표시 for j in range(x1,x2): for k in range(y1,y2): background[k][j] =1 def solve(): init() numof_area = 0 for i in range(m): for j in range(n): if background[i][j] == 0: solve_q.append((i,j)) background[i][j]=1 area = 1 while(solve_q): a,b = solve_q.pop(0) direct =[(a+1,b),(a,b+1),(a-1,b),(a,b-1)] //위,아래 , 왼쪽, 오른쪽 for s in direct: //배열을 돌면서 조건에 벗어나면 skip, 아니라면 리스트에 넣기 if s[0]>=0 and s[0]<m and s[1]>=0 and s[1]<n : if background[s[0]][s[1]] !=1: solve_q.append(s) background[s[0]][s[1]] =1 area+=1 result.append(area) numof_area+=1 result.sort() print(numof_area) b = map(str, result) print(' '.join(b)) solve() <p> </p>