https://www.acmicpc.net/problem/2583
2583번: 영역 구하기
첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오
www.acmicpc.net
import sys
# 전체 - 직사각형 => 빈 좌표 집합
def sorting_empty_coordinate_set(m,n,k):
false_set, true_set = set(), set()
for _ in range(k):
x1,y1, x2,y2 = map(int, sys.stdin.readline().rstrip().split())
for y in range(y1,y2):
for x in range(x1,x2):
false_set.add((x,y))
for y in range(0,n):
for x in range(0,m):
true_set.add((x,y))
return true_set - false_set
# dfs로 풀기 위해 인접 노드 딕셔너리 만들기
def set_to_adj_dic(coor_set):
coor_dic, coor_adj_dic = dict(), dict()
for xy in coor_set:
coor_dic[xy] = True
for xy in coor_set:
tm_adj_list = []
if coor_dic.get((xy[0]+1,xy[1]), False): tm_adj_list.append((xy[0]+1,xy[1]))
if coor_dic.get((xy[0]-1,xy[1]), False): tm_adj_list.append((xy[0]-1,xy[1]))
if coor_dic.get((xy[0],xy[1]+1), False): tm_adj_list.append((xy[0],xy[1]+1))
if coor_dic.get((xy[0],xy[1]-1), False): tm_adj_list.append((xy[0],xy[1]-1))
coor_adj_dic[xy] = tm_adj_list
return coor_adj_dic, coor_dic
# dfs로 풀기
# 처음에 list형식 사용했다가 시간초과로 set으로 바꿈
# set = 해시 O(1), list = 동적 배열 O(n)
def dfs(graph, start, coor_dic):
result, visit = set(), []
visit.append(start)
while visit:
node = visit.pop()
if node not in result:
result.add(node)
visit.extend(graph[node])
coor_dic.pop(node,0)
return result
if __name__ == '__main__':
result,sol = [],[]
N,M,K = map(int, sys.stdin.readline().rstrip().split())
adj_dic, coor_dic = set_to_adj_dic(sorting_empty_coordinate_set(M,N,K))
while coor_dic:
tm = coor_dic.popitem()
sol = dfs(adj_dic, tm[0], coor_dic)
result.append(len(sol))
print(len(result))
sys.stdout.write(' '.join(map(str,sorted(result))))
'백준 & 프로그래머스' 카테고리의 다른 글
백준.아기 상어2.17086.py (0) | 2023.09.19 |
---|---|
백준.유기농 배추.1012.py (0) | 2023.09.19 |
백준.바이러스.2606.py (0) | 2023.09.15 |
백준.등수 구하기.1205.py (0) | 2023.09.13 |
백준.11724.연결 요소의 개수.py (0) | 2023.09.12 |
댓글