백준 1012번 파이썬 _ 유기농배추

www.acmicpc.net/source/26224365

로그인

문제유형 : DFS/BFS _ connected component찾기

문제핵심 : 한칸의 땅을 노드로 하고 상하좌우로 연결을 갖는 그래프라고 생각하고 각 노드마다 DFS를 수행하여 처음 DFS를 시작한부분에서만 카운트

 

DFS수행방법 : 하나의 노드는 상하좌우로 연결되어있다고 생각하고 해당 노드가 1이면서 방문되지 않았을때 ( 배추가 심어져있으면서 방문전이면 ) 방문처리+ 상하좌우로 움직여서 다시 해당노드에서 재귀적으로 DFS수행

그래프는 2차원배열로 구현한 좌표평면의 형태이며, 움직일때마다 움직인곳이 좌표평면을 넘어가면 안되므로 그부분만 예외처리를 해주면된다.

 

처음 DFS를 시작한부분에서만 카운트하는 방법 : DFS를 통해 처음으로 방문하게된 노드에서만 True를 반환하고 나머지 (재귀적으로 호출되는 노드) 들에서는 False를 리턴함으로써 하나의 덩어리(?) 마다 한번의 True를 리턴할수있도록 한다.

 

기억해야할것 :

1. 2차원배열을 4사분면 그래프처럼 표현하는경우 좌표로 (x,y) ==> 배열 [y][x]임을 꼭 기억할것

2. 파이썬에서 재귀깊이가 제한되어 있으므로 Recursion Error를 방지하기 위해 sys.setrecursionlimit(10**6)을 추가해줄것

3. 상하좌우로 움직이는 문제는 내가푼것처럼move배열을 두거나 dx, dy등의 좌표배열을 두고 활용할것

4. 경계를 확인할때는 넘어가는부분을 or로 확인하는것이 편함 ( 좌표안에 포함되는 조건 +and 보다 좌표를 벗어나는 조건 + or)로 

t = int(input())

import sys
sys.setrecursionlimit(10**6)

move = [[1,0],[0,1],[-1,0],[0,-1]]
count = 0
answer = []

def dfs(graph, x, y, visited ):
    if graph[y][x] == 1 and visited[y][x] == False: #배추가 심어져 있으면서 아직 방문하지 않았으면
        visited[y][x] = True

        for i in range(4):
            if (x + move[i][0]) < 0 or (x + move[i][0]) >= m or (y + move[i][1]) < 0 or (y + move[i][1]) >= n:
                continue
            else:
                dfs(graph, x + move[i][0], y + move[i][1], visited)
        return True
    return False

for _ in range(t):
    m,n,k = map(int, input().split())

    graph = [[0] * m for _ in range(n)] # m*n배열

    visited = [[False] * m for _ in range(n)]

    for _ in range(k):
        x,y = map(int, input().split())
        graph[y][x] = 1

    for line in range(n): # 0~7
        for base in range(m):
            x,y = base, line #좌표로 x, y --> 좌표를 표현한 2차원 배열에서는 배열[y][x]
            if dfs(graph, x, y, visited) == True:
                count += 1

    answer.append(count)
    count = 0

for i in answer:
    print(i)

다른분코드

움직일때마다 움직인 방향으로의 경계만 확인하여 그쪽으로 움직였을때 넘어갔는지 확인함

나보다 더 간단함

 

움직여도 경계를 벗어나지 않으면서 + 배추가 심어져있다면 1을 0으로 바꿔주어 방문처리까지 간단하게 해버림

이렇게하면 배추가 심어져있음을 뜻하는 1은 동시에 방문이 아직 안됬음을 의미하게됨

import sys;p=sys.stdin.readline;
sys.setrecursionlimit(1000000)
q=int(p())
def T(t, o, s):
    t[s][o]=0
    if o+1 < x and t[s][o+1]==1:
        T(t,o+1,s)
    if o-1>= 0 and t[s][o-1]==1:
        T(t, o-1,s)
    if s -1 >= 0 and t[s-1][o]==1:
        T(t, o,s-1)
    if s +1 < y and t[s+1][o]==1:
        T(t,o,s+1)

for _ in range(q):
    x, y, c = map(int, p().split())
    t = [[0] * x for _ in range(y)]
    for i in range(0,c):
        m,n=map(int,p().split());t[n][m] = 1
    v = 0
    for i in range(0,x):
        for j in range(0, y):
            if t[j][i] == 1:
                T(t, i, j);v+=1
    print(v)