[백준] 2583 파이썬(python) : 영역 구하기 - (범위색칠)

2583번: 영역 구하기

 

 

 

기존의 bfs/dfs 문제와의 차이점은 영역 하나하나를 그래프 내에 범위로 주어진다는 것이다. 그것을 그래프 위에 구현하기만 하면 다른 문제들과 같아진다. 그래프 위에 범위를 색칠한다고 표현하겠다.

 

dfs를 이용한 나의 풀이)

import sys
sys.setrecursionlimit(10**5)
from collections import deque
m, n, k = map(int, sys.stdin.readline().split())
graph = [ [0]*n for _ in range(m) ] #1
for _ in range(k):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split()) #2
    for i in range(y1, y2): #3
        for j in range(x1, x2): #4
            graph[i][j] = -1 #5
res = []
visit = [[False]*(n+1) for _ in range(m+1) ]
dx = [ -1, 1, 0, 0 ]
dy = [ 0, 0, -1, 1 ]

def dfs(x, y):
    global cnt
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < m and 0 <= ny < n and graph[nx][ny] == 0:
            if not visit[nx][ny]:
                visit[nx][ny] = True
                cnt += 1
                dfs(nx, ny)
for i in range(m):
    for j in range(n):
        if not visit[i][j] and graph[i][j] == 0:
            cnt = 1
            visit[i][j] = True
            dfs(i, j)
            res.append(cnt)
print(len(res))
res.sort()
print(*res)

 

#1 : 가로, 세로가 n, m이 아닌 m, n으로 들어오므로 반대로 입력

#2 : 왼쪽 아래, 오른쪽 위의 점이 x1, y1, x2, y2로 들어온다

#3 : 주어진 범위안의 내용을 모두 색칠해야 하므로 범위를 가지고 반복문을 돌림

#4 : y가 행이고 x가 열이므로 y가 더 상위 반복문이 된다.( y는 m x는 n)

#5 : 그래프하는 색칠을 -1로 덮어씌운것으로 표현

 

 

 

다른 bfs풀이 - 23.01.17(화)

import sys
from collections import deque
m, n, k = map(int, sys.stdin.readline().split())
graph = []
visit = [ [False]*(n) for _ in range(m) ]
for _ in range(k):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    for i in range(m-y2, m-y1): #1
        for j in range(x1, x2): #2
            visit[i][j] = True
dx = [ 0, 0, -1, 1 ]
dy = [ -1, 1, 0, 0 ]
count = 0
arr = []
def bfs(x, y):
    global cnt
    q = deque()
    q.append((x, y))
    visit[x][y] = True
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n and visit[nx][ny] == False:
                visit[nx][ny] = True
                q.append((nx, ny))
                cnt += 1
    return cnt
for i in range(m):
    for j in range(n):
        if visit[i][j] == False:
            cnt = 1
            arr.append(bfs(i, j))
            count += 1
print(count)
arr.sort()
print(*arr)

 

#1: 왼쪽 아래부터 (0, 0)인것을 고려해서 반복문을 돌때는 왼쪽 위부터 돌기 시작하므로 세로축은 y2 ~ y1이 범위가 된다(반대가 된다).

#2: 가로축은 x1 ~ x2가 된다.