https://www.acmicpc.net/problem/1012
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
1. 내가 작성한 코드
1. BFS풀이
from collections import deque
def bfs(matrix, x,y):
queue = deque()
queue.append((x,y))
matrix[x][y] = 0
while queue:
x,y = queue.popleft()
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >=n or ny >=m:
continue
if matrix[nx][ny] == 0:
continue
if matrix[nx][ny] == 1:
queue.append((nx,ny))
matrix[nx][ny] = 0
t = int(input())
for i in range(t):
cnt = 0
m,n,k = map(int, input().split())
matrix = [[0] * m for i in range(n)]
for i in range(k):
m,n = map(int, input().split())
matrix[n][m] = 1 ###고침
for i in range(n):
for j in range(m):
if matrix[i][j] == 1:
cnt += 1
bfs(matrix, i, j)
print(cnt)
+
2. DFS풀이
import sys
sys.setrecursionlimit(1000000)
def dfs(x,y):
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx>=b or ny>=a:
continue
if maps[nx][ny] == 1:
maps[nx][ny] = 0
dfs(nx,ny)
return True
t = int(input())
for _ in range(t):
cnt = 0
a,b,c = map(int, input().split()) #a가로 b세로 c배추
maps = [[0] * a for _ in range(b)]
for _ in range(c):
d,e = map(int, input().split())
maps[e][d] = 1
for i in range(b):
for j in range(a):
if maps[i][j] == 1:
maps[i][j] = 0
dfs(i,j)
cnt+=1
print(cnt)
메모
처음에 visit라는 2차원 배열을 할당해서 방문 여부를 확인했으나,
그냥 1을 0으로 바꿔서 더 효율적으로 풀 수 있는 문제였다.
'🔅코딩테스트 공부🔅 > ❗백준' 카테고리의 다른 글
[백준] 7562번 나이트의 이동(python) (0) | 2023.02.10 |
---|---|
[백준] 24416번 알고리즘 수업 - 피보나치 수 1(python) (0) | 2023.02.09 |
[백준] 24444번 너비 우선 탐색 1(with python) (0) | 2023.02.08 |
[백준] 2667번 단지번호붙이기(with python) (0) | 2023.02.08 |
[백준] 2606번 바이러스(with python) (0) | 2023.02.08 |
댓글