[2022-03-24] 유기농 배추

푼 시간 : 2시간정도 ( 잘 모름.. )

언어 : 파이썬

---

 

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

대충 그래프 문제

이제 코딩테스트 준비를 진짜 해야되서

풀면서 힌트가 될만한 문제는 다시 스크랩을 할 예정이다.

내가 푼 문제니까 다시 보면 아 이런 문제는 이런 유형이구나

하고 기억할거같아서 다시 넣는다.

 

# 백준 1012번 유기농 배추
# 2시간은 걸린듯
# 파이썬은 2차원 배열을 선언하면서 시간이 오래걸린다. (2차원 배열의 객체크기가 클경우)
# 객체 생성의 횟수가 적은쪽이 유리하다.
# 시간 제한이 짧다면 visited를 선언하지않고 푸는것을 추천..
# 그리고 dx, dy 더하고 빼는건 좌표 문제에서 필수적으로 기억할 것

import sys
from collections import deque

dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(graph, starty, startx):
    queue = deque()
    queue.append((starty, startx))
    graph[starty][startx] = 0
    
    while queue:
        starty, startx = queue.popleft()
        
        for i in range(4):
            ny = starty + dy[i]
            nx = startx + dx[i]
            
            if ny >= n or ny < 0 or nx >= m or nx < 0:
                continue
            
            if graph[ny][nx] == 1:
                graph[ny][nx] = 0
                queue.append((ny, nx))
                
    return

testcase = int(sys.stdin.readline())
answer = [0] * testcase

for i in range(testcase):
    m, n, k = map(int, sys.stdin.readline().split())
    x, y = 0, 0
    graph = [[0 for i in range(m)] for j in range(n)]
    stack = [0] * (k*2)
    count = 0
    
    for j in range(k):
        posx, posy = map(int, sys.stdin.readline().split())
        graph[posy][posx] = 1
        stack[count] = posy
        stack[count+1] = posx
        count += 2
        
    for j in range(0, len(stack), 2):
        if graph[stack[j]][stack[j+1]] == 1:
            bfs(graph, stack[j], stack[j+1])
            answer[i] += 1

for i in range(testcase):
    print(answer[i])

 

참고로 이 경우는 내가 다른분이 정리해놓은

이차원 리스트를 선언할 때 [[0 for i in range(m)] for j in range(n)]를 보고

[y, x]로 한것인데 이거 말고 [x, y]로 하려면

 

import sys
from collections import deque

dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(graph, startx, starty):
    queue = deque()
    queue.append((startx, starty))
    graph[startx][starty] = 0
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx >= n or nx < 0 or ny >= m or ny < 0:
                continue
            
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))
                
    return

testcase = int(sys.stdin.readline())
answer = [0] * testcase

for i in range(testcase):
    n, m, k = map(int, sys.stdin.readline().split())
    graph = [[0]*m for i in range(n)]
    stack = [0] * (k*2)
    count = 0
    
    for j in range(k):
        posx, posy = map(int, sys.stdin.readline().split())
        graph[posx][posy] = 1
        stack[count] = posx
        stack[count+1] = posy
        count += 2
        
    for j in range(0, len(stack), 2):
        if graph[stack[j]][stack[j+1]] == 1:
            bfs(graph, stack[j], stack[j+1])
            answer[i] += 1

for i in range(testcase):
    print(answer[i])

 

graph = [[0]*m for i in range(n)]를 사용하고,

이렇게 x, y를 썼다.

그래프 개같다.