둔필승총

www.acmicpc.net/problem/1012

[문제 풀이]

문제가 길지만 정리하자면 배추밭에서 1이 있는곳은 배추가 있는곳, 0은 배추가 없는 곳이다. 1이 있는 곳을 DFS해서 주위에 0으로 둘러쌓일때까지 구하고, 그 갯수를 파악해서 출력하면 된다. 혹은 BFS를 통해서 풀 수 있다. (복습을 할 때 BFS를 통해서 풀었다.)

1. 첫번째 풀이법

import sys
sys.setrecursionlimit(10000)
def dfs(x,y):
    if x<=-1 or x>=n or y<=-1 or y>=n:
        return False
    if graph[x][y]==1:
        graph[x][y]=0
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x,y-1)
        return True
    return False
t = int(input())
for _ in range(t):
    m,n,k=map(int,input().split())
    graph=[[0]*(m) for _ in range(n)]
    result=0
    for _ in range(k):
        x,y=map(int,input().split())
        graph[y][x]=1
    for i in range(n):
        for j in range(m):
            if dfs(i,j):
                result+=1
    print(result)

dfs 함수를 정의해 주면서 먼저 x와 y좌표가 범위를 벗어날때는 False를 반환하게 두었다. 그러나 이렇게 하면 만약 x,y 에 (0,0) 이 들어갔을 경우 index error가 일어나게 된다. 

2. 두번째 풀이법

import sys
sys.setrecursionlimit(10000)
def dfs(x,y):
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    for i in range(4):
        nx,ny = x+dx[i],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
            dfs(nx,ny)
t = int(input())
for _ in range(t):
    m,n,k=map(int,input().split())
    graph=[[0]*(m) for _ in range(n)]
    result=0
    for _ in range(k):
        x,y=map(int,input().split())
        graph[y][x]=1
    for i in range(n):
        for j in range(m):
            if dfs(i,j):
                result+=1
    print(result)

두 번째 풀이법은 dx, dy를 통해서 상하좌우를 탐색하기 때문에 상관없지만 첫번째 풀이법은 의도치 않은 인덱스에 접근할 수 있기때문에 오류가 난다.

3. 세번째 풀이 (BFS를 통해서 해결)

BFS를 통해서 푸는 것으로 익숙해질려고 했다.(DFS를 사용하니까 계속 recursion error 같은 것들을 신경써야해서..) 먼저 BFS는 deque를 사용하므로 상단에 deque를 import 시켜준다.

from collections import deque

bfs는 파라미터로 a,b를 받는다. 여기서 a, b는 배추밭에서 1인 것, 즉 배추가 있는곳을 찾으면 bfs를 실행해서 주위가 0으로 둘러쌓인것에 닿을때까지 실행해준다. 그리고 bfs함수가 끝나면 total_num(우리가 출력해야 되는 값)을 하나 더해준다.

 매번 헷갈리지만 주의해야 할 것은 2차원 배열에 x,y축의 값이다.. 가로가 m이지만 배열의 첫번째는 y축의 값이 들어가는.. 이런것을 계속 생각해주어야 한다. 

from collections import deque
def bfs(a,b):
    q=deque([])
    q.append((a,b))
    graph[a][b]=0
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    bechu = 0
    while q:
        x,y=q.popleft()
        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 and graph[nx][ny]==1:
                q.append((nx,ny))
                graph[nx][ny]=0
t = int(input())
for _ in range(t):
    m,n,k = map(int,input().split())
    graph=[[0]*(m) for _ in range(n)]
    total_num = 0
    for i in range(k):
        x,y = map(int,input().split())
        graph[y][x]=1
    for i in range(n):
        for j in range(m):
            if graph[i][j]==1:
                bfs(i,j)
                total_num+=1
    print(total_num)