백준 1012 풀이 (유기농 배추, DFS, 행렬)

2667번과 아주 흡사하다.(guccin.tistory.com/89?category=977502)

그나마 다른점은 정사각형 행렬이 아니라 직사각형 행렬이라는점 뿐이다. 그래서 2667의 DFS함수를 그대로 가져와서 사용할 수 있었다.

코드는 2667과 거의 유사하고 다른점은 배추의 포인트를 직접 갱신 시켜준다는 점과 패딩을 직사각형에 맞춰주는 것 밖에는 없다.

그래서 2667을 이해하면 그냥 껌이 되버리는 문제이다.

 

풀이 쓰는 시간이 아까우니 바로 코드를 첨부한다.

def DFS(i, j, L):
    stack = [(i,j)]
    out = []
    while stack:
        t = stack.pop()
        a,b = t
        if t not in out:
            out.append(t)
            L[a][b] = 0 # 지워버려
            #위쪽 오른쪽 위 아래
            tmp = []
            if L[a][b-1] == 1:
                tmp += [(a,b-1)] 
            if L[a][b+1] == 1:
                tmp += [(a,b+1)]
            if L[a+1][b] == 1:
                tmp += [(a+1, b)]
            if L[a-1][b] == 1:
                tmp += [(a-1,b)]
            tmp = list(set(tmp) - set(out))
            stack += tmp
    return len(out)
# main
case = int(input())
for _ in range(case):
    m,n,p = map(int, input().split())
    L = [[0 for i in range(m)] for i in range(n)]
    for i in range(p):
        a,b = map(int, input().split())
        L[b][a] = 1
    for i in range(n):
        L[i] = [0] + L[i] + [0]
    L = [[0 for i in range(m+2)]] + L + [[0 for i in range(m+2)]]
    num = []
    for i in range(n):
        for j in range(m):
            if L[i+1][j+1] == 1:
                num.append(DFS(i+1,j+1,L))
    print(len(num))
        

 

스터디 때문에 다시 한번 풀어보았다.

이번에도 패딩은 제거하고 인덱스를 검증하고 배추가 존재하는지 검증하여 풀이를 진행했다.

t = int(input())

def dfs(i,j):
    stack = [[i,j]]
    dx = [0,0,1,-1] #동서남북    
    dy = [1,-1,0,0]    
    while len(stack) != 0:
        x,y = stack.pop()
        Map[x][y] = 0
        for _ in range(4):
            nx = x + dx[_]
            ny = y + dy[_]
            if nx<n and ny<m and nx>=0 and ny>=0:
                if Map[nx][ny] == 1:
                    stack.append([nx,ny])

for _ in range(t):
    m,n,k  = map(int, input().split())
    Map = [[0 for i in range(m)] for i in range(n)]
    for i in range(k):
        x,y = map(int, input().split())
        Map[y][x] = 1
    count = 0
    for i in range(n):
        for j in range(m):
            if Map[i][j] == 1:
                dfs(i,j)
                count+=1
    print(count)

이번에 이렇게 풀었더니 시간도 반이나 줄고 코드도 줄어들어서 기뻤다.