https://www.acmicpc.net/problem/2583
입력이.. 더러웠다.. 그리고 내 풀이도.. ,.
진심 넘 더럽게 풀어서 다시 풀어야 할 것 같다.
우선 입력을 받아서 maps
그래프를 만들어주었다.
그래프는 0으로 초기화 해주고, 직사각형의 범위만 1로 바꿨다.
m = 행의 개수, n = 열의 개수, k = 직사각형 수
m, n, k = map(int, input().rsplit())
maps = [[0 for _ in range(n)] for _ in range(m)]
dst = defaultdict(list)
for _ in range(k):
y1, x1, y2, x2 = map(int, input().rsplit())
for i in range(x1, x2):
for j in range(y1, y2):
maps[i][j] = 1
상하좌우로 이동하면서 직사각형이 아닌 구역을 체크한 뒤 dst
인접 리스트로 연결해주었다.
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for x, rows in enumerate(maps):
for y, char in enumerate(rows):
if char == 0:
dst[(x, y)].append((x, y))
for t in range(4):
nx = dx[t] + x
ny = dy[t] + y
if (0 <= nx < m and 0 <= ny < n and maps[nx][ny] == 0):
dst[(x, y)].append((nx, ny))
dfs 함수로 이동할 때마다 cnt에 1씩 더해줬고 0을 1로 바꾸어주었다. 계속 이동하다가 더 이상 이동할 수 없으면 cnt를 반환해주었다.
만약 이미 방문한 곳이면 False를 반환해주었다.
def dfs(x, y):
global cnt
cnt += 1
if maps[x][y] == 0:
maps[x][y] = 1
for (nx, ny) in dst[(x, y)]:
if maps[nx][ny] == 0:
dfs(nx, ny)
else:
return False
return cnt
False가 아닌 cnt가 반환될 때마다 ground
구역의 수를 1씩 증가시켰다.
cnt는 result
리스트에 추가해주었다.
ground = 0
result = []
for x, y in dst:
cnt = 0
answer = dfs(x, y)
if answer:
ground += 1
result.append(answer)
result.sort()
print(ground)
print(' '.join(map(str,result)))
import sys
from collections import defaultdict
sys.setrecursionlimit(100001)
input = sys.stdin.readline
m, n, k = map(int, input().rsplit())
maps = [[0 for _ in range(n)] for _ in range(m)]
dst = defaultdict(list)
for _ in range(k):
y1, x1, y2, x2 = map(int, input().rsplit())
for i in range(x1, x2):
for j in range(y1, y2):
maps[i][j] = 1
# for row in maps:
# print(row)
# print()
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for x, rows in enumerate(maps):
for y, char in enumerate(rows):
if char == 0:
dst[(x, y)].append((x, y))
for t in range(4):
nx = dx[t] + x
ny = dy[t] + y
if (0 <= nx < m and 0 <= ny < n and maps[nx][ny] == 0):
dst[(x, y)].append((nx, ny))
# print(dst)
cnt = 0
def dfs(x, y):
global cnt
cnt += 1
if maps[x][y] == 0:
maps[x][y] = 1
for (nx, ny) in dst[(x, y)]:
if maps[nx][ny] == 0:
dfs(nx, ny)
else:
return False
return cnt
ground = 0
result = []
for x, y in dst:
cnt = 0
answer = dfs(x, y)
if answer:
ground += 1
result.append(answer)
result.sort()
print(ground)
print(' '.join(map(str,result)))