[알고리즘] 백준 1012 : 유기농 배추 - S2

2023.05.09 풀이

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**8)

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

def dfs(x,y):
    if x<0 or x>=n or y<0 or y>=m:
        return False
    if arr[x][y]==1:
        arr[x][y]=0
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            dfs(nx, ny)
        return True
    return False

t=int(input())
for _ in range(t):
    m,n,k=map(int, input().split())
    arr=[[0]*(m) for _ in range(n)]
    for _ in range(k):
        x,y=map(int, input().split())
        arr[y][x]=1

    cnt=0
    for i in range(n):
        for j in range(m):
            if dfs(i,j)==True:
                cnt+=1
    print(cnt)

• 마지막 2중반복문 부분이 좀 헷갈렸음

  배추가 심어져있는 총 개수를 세는게 아니라
  배추가 심어져있는 부분의 개수 카운트하면 되기 때문에,
  전부 탐색하다가 배추 부분을 처음 만날 부분은 True를 리턴(처음 이후는 재귀로 False를 리턴하기 때문) - True의 개수를 카운트 해주면 됨.

• 전부 탐색해야하므로 dfs로 판단하였으나, bfs도 가능.

2023.05.26 풀이

import sys
input=sys.stdin.readline

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

def dfs(x,y):
    if arr[x][y]==1:
        arr[x][y]=0
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx>=0 and nx<n and ny>=0 and ny<m:
                dfs(nx, ny)
        return True
    return False

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

    arr=[[0]*(m) for _ in range(n)]
    for _ in range(k):
        a, b=map(int, input().split())
        arr[b][a]=1

    cnt=0
    for i in range(n):
        for j in range(m):
            if dfs(i, j)==True:
                cnt+=1
    print(cnt)

• arr 범위 지정하는 부분 조심하기.
  가로 세로 변수 확인 잘 하고, +1 줘도 되는지 여부 잘 확인하기
• 25번째 줄 arr[][]=1이 조금 생소했는데, arr[].append() 랑 차이 주의하기
  -> 2606, 11724 문제 참고
• dfs 재귀 깊이 제한 깜박하지말기..

다른 풀이

-
def dfs(x, y):
  arr[x][y] = 0
  for a in range(4):
    nx = x + dx[a]
    ny = y + dy[a]
    if (0 <= nx and nx < n) and (0 <= ny and ny < m):
      if arr[nx][ny] == 1:
        dfs(nx, ny)
 -
 for i in range(n):
  for j in range(m):
    if field[i][j] == 1:
      dfs(i, j)
      cnt += 1

check point

• dfs 재귀 제한 ! -> sys.setrecursionlimit()
• 문제에서 구하려는게 총 개수인지, 부분의 개수인지 판별.