[Python3] 백준 1012번 유기농 배추

사용 언어 - Python3

문제 - 유기농 배추

1012번: 유기농 배추

 

정답

nx,ny 이동하는 BFS 만들기 (정답 맞춘 여부 X)

0. 입력

배추밭 graph(m행*n열)에 graph[x][y] = 1로 배추표시

 

1. queue를 사용한 BFS(x,y)

visit 리스트를 만들지 않아도, grpah의 0과 1로 방문표시가 가능하다.

graph[x][y] = 0 방문처리

graph[x][y] = 1 방문하지 않은, 배추가 있는 곳

 

x,y를 상하좌우로 이동시켜 nx,ny의 새로운 위치에서 graph[x][y]=1이라면 queue에 append하고 방문처리

 

2. 출력

BFS(x,y)를 한번 돌때마다 즉, (x,y)의 상하좌우를 모두 다 이동시키고 더이상 주변에 배추가 없을 때

cnt += 1을 해주고, 새로운 (x,y)로 이동한다.

정답은 전체 (x,y)를 돌고 난 후, 최종 cnt이다.

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

def BFS(x,y):           
    queue = [(x,y)]
    graph[x][y] = 0 # 방문처리

    while queue:
        x,y = queue.pop(0)

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= M or ny < 0 or ny >= N:
                continue

            if graph[nx][ny] == 1 : #방문하지 않았다면
                queue.append((nx,ny))
                graph[nx][ny] = 0

T = int(input()) #테스트케이스의 개수
for i in range(T):
    M, N, K = map(int,input().split()) #배추밭 가로길이, 세로길이, 배추위치
    graph = [[0]*(N) for _ in range(M)]
    cnt = 0

    for j in range(K):
        x,y = map(int, input().split()) #배추좌표
        graph[x][y] = 1 #배추 있다는 표시

    for a in range(M):
        for b in range(N):
            if graph[a][b] == 1:
                BFS(a,b)
                cnt += 1

    print(cnt)

 

 

 

---

레퍼런스

• 정답 참고

[백준][Python] 1012번 유기농 배추

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부