https://www.acmicpc.net/problem/14716
시간 2초, 메모리 512MB
input :
- M N 공백으로 구분(1 <= M, N <= 250)
- 1, 0의 정보 입력
output :
- 글자의 개수 출력
조건 :
- 글자인 부분 1, 글자가 아니면 0
- 1인 자리에서 상, 하, 좌, 우, 대각선으로 인접해 서로 연결이 되면 한 개의 글자
상하좌우의 벡터.
y = [-1, 1, 0, 0]
x = [0, 0, -1, 1]
대각선의 벡터(상좌, 상우, 하좌, 하우)
y = [-1, -1, 1, 1]
x = [-1, 1, -1, 1]
2차원 리스트를 제일 위에서 부터 돌면서 1인 지점을 찾으면 BFS에 집어 넣은 후
그 자리를 0으로 바꾸어 줌.
그리고 위의 벡터의 경우를 다 집어 넣어 1을 만나면 큐에 추가.
BFS가 끝나면 글자의 개수를 1개 올려주는 방식.
--> BFS의 방식으로 접근 하는 것이 틀린 것인지. 시간초과 메모리 초과 런타임 에러 삼위일체의 공격을 받음.
DFS로 풀어보자..
if 조건문도 수정이 필요.
if 0 <= x <= M and 0 <= y <= N and graph[nx][ny]:
dfs(nx, ny)밖을 나가는 것을 판단하는 것이 시간적으로 이득을 주는 것 같다.
if nx < 0 or nx >= N or ny < 0 or ny >= M:
continue재귀의 상한선을 걸어줘야 런타임 에러에 빠지지 않는다.
import sys
sys.setrecursionlimit(100000)정답 코드 :
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
ans = 0
def dfs(x, y):
graph[x][y] = 0
dy = [-1, 1, 0, 0, -1, -1, 1, 1]
dx = [0, 0, -1, 1, -1, 1, -1, 1]
for i in range(len(dy)):
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]:
dfs(nx, ny)
for i in range(N):
for j in range(M):
if graph[i][j]:
dfs(i, j)
ans += 1
print(ans)
화려한 공격을 받은 채점 결과.
왜 DFS는 풀리고, BFS는 안 되는 건지 탐구해보자.
