[1012번] 유기농 배추 with Python (★)

문제

 

내가 작성한 코드 (틀림)

import sys
input = sys.stdin.readline

def dfs(x, y, visited, graph):
    cnt = 0
    if x < 0 or y < 0 and x >= m and y >= n:
        break
    if visited[x][y] == False and graph[x][y] == 1:        
        visited[x][y] = True
        for i in range(1, 5):
            dfs(x + dx[i], y + dy[i], visited)
        cnt += 1
        return cnt
    else:
        for i in range(1, 5):
            dfs(x + dx[i], y + dy[i], visited)
                
# Test CAse 수
t = int(input())

# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(t):    
    # 가로길이(M), 세로길이(N), 위치의 개수(K)
    m, n, k = map(int, input().split())

    # 배추밭
    graph = [ [0] * m for _ in range(n) ]
    visited = [ [0] * m for _ in range(n) ]
    for i in range(k):
        m_v, n_v = map(int, input().split())
        graph[m_v][n_v] = 1
    print(dfs(0, 0, visited, graph))

> 저는 dfs 로 풀려고 했는데... bfs 공식 코드는 외우고 있는데 이거를 문제에 적용시키는 것은 또 다른 문제임을 깨달았습니다. ㅜㅜ

> 더 공부하자!!!

 

참고한 코드

from collections import deque

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

t = int(input())

def bfs(graph, a, b):
    queue = deque()
    queue.append((a,b))
    graph[a][b] = 0

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

for i in range(t):
    cnt = 0
    n, m, k = map(int,input().split())
    graph = [[0]*m for _ in range(n)]

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

    for a in range(n):
        for b in range(m):
            if graph[a][b] == 1:
                bfs(graph, a, b)
                cnt += 1
    print(cnt)

> 참고한 블로그

https://hongcoding.tistory.com/72

[백준] 1012 유기농 배추 (Python 파이썬)

 

내가 해보는 코드 작성

from collections import deque

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

> 위 모듈 불러오는 것은 아래 코드 작성에 있어서 bfs는 큐 함수를 필요하기 때문에 deque 모듈을 불러옵니다.

> dx, dy는 상, 하, 좌, 우 방향 이동할 때 필요로 하는 코드입니다.

 

t = int(input())

def bfs(graph, a, b):
    queue = deque()
    queue.append((a,b))
    graph[a][b] = 0

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

> t 변수는 테스트 케이스 값을 입력받기 위한 코드입니다.

> 본격적인 bfs 코드 함수 코드입니다.

> graph는 배추밭에 배추 위치가 입력되어 있는 변수입니다. 그리고 a, b는 배추 위치 값 코드를 의미합니다.

> deque() 함수를 통해 그 위치 값을 queue 변수에 받고, graph[a][b]는 배추 위치가 있는 값으로 1인데 그 값을 0으로 바꿔줍니다. 이는 마지막 개수를 세기 위해서 주변에 존재하는 배추 위치를 제거하기 위한 코드입니다.

> while 문(반복문)을 사용하여 상,하,좌, 우로 값을 적용하여 배추 위치가 있는 곳은 0으로 바꾸고 아닌 곳은 continue로 뛰어넘게 작성한 것입니다.

 

for i in range(t):
    cnt = 0
    n, m, k = map(int,input().split())
    graph = [[0]*m for _ in range(n)]

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

    for a in range(n):
        for b in range(m):
            if graph[a][b] == 1:
                bfs(graph, a, b)
                cnt += 1
    print(cnt)

> 반복문을 사용하여 test case 개수만큼 n,m,k, graph 값을 받습니다.

> 그리고 다시 한 번 이중반복문을 적용하여 주어진 행과 열만큼 일일이 graph[a][b] == 1인 개수를 세어 최종 출력하기 위한 cnt 값을 출력합니다.

> 여기서 cnt 값은 위에서 설명한 bfs 함수를 통해서 한 배추 위치 근처에 있는 배추들은 오로지 하나의 배추 위치 값만 남게 하기 때문에 정확한 값을 추출할 수 있게됩니다.

> bfs, dfs 코드를 외우는 것도 중요하지만, 문제에 맞게 적용하는게 더 중요하다!! 더 공부!!!