[백준] 16946 : 벽 부수고 이동하기 4

BFS

문제 : 벽 부수고 이동하기 4

1번 풀이 방법: 벽을 만나면 DFS 돌려서 답을 출력하려고 했는데 역시나~ O((N+M)NM) 시간초과~
2번 방법: 벽을 만나면 BFS 돌려서 답을 출력하려고 했는데 역시나~ O((N+M)NM) 시간초과
3번 풀이방법: 그룹 지어서 벽 만나면 좌우상하의 그룹 값 더하기 -> DFS로 구현하면 메모리 초과
4번 풀이방법: 2번 방법으로 하되, BFS로 구현 -> 통과~ O(NM+(N+E))
시간초과, 메모리 초과 때문에 애 먹은 문제입니다. ㅡ ㅅ ㅡ,,

문제 풀이 핵심은 1이 아니라 0이 몇개 모여있는지 키-밸류로 순서:값 으로 저장하고 반복문을 돌면서
벽이 나오면(1이나오면) 상하좌우에 있는 0그룹의 갯수를 더하는 것입니다.
그러면 시간 복잡도가 O(NM+(N+E))으로 현저히 줄어들어서 시간초과를 해결 할 수 있습니다.

1번 풀이(시간초과) :

import sys
input  = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for i in range(n):
	graph.append(list(map(int, sys.stdin.readline().rstrip())))
#최종 답 출력 배열
answer = [[0]*m for _ in range(n)]
def dfs(x, y):
	global each
	if x < 0 or y < 0 or x >= n or y >= m:
		return False
	if graph[x][y] == 0 and not visited[x][y]:
		visited[x][y] = True
		dfs(x-1, y)
		dfs(x+1, y)
		dfs(x, y+1)
		dfs(x, y-1)
       		#그룹 안의 몇개가 있는지 구현
		each += 1
		return True
	return False
for i in range(n):
	for j in range(m):
    		#리셋
		each = 0
        	#방문여부 리셋
		visited = [[False] * m for _ in range(n)]
        	#1이면 0으로 치환(벽 부수는일) -> dfs -> 다시 원래 대로 돌려 (다음 것 실행하기 위해)
		if graph[i][j] == 1:
			graph[i][j] = 0
			if dfs(i, j) == True:
				answer[i][j] = each
				graph[i][j] = 1
		else:
			continue
for i in range(n):
	for j in range(m):
		print(answer[i][j], end='')
	print()

2번풀이 (시간 초과)

import sys
from collections import deque
input  = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for i in range(n):
	graph.append(list(map(int, sys.stdin.readline().rstrip())))
answer = [[0]*m for _ in range(n)]
dx = [-1, 1, 0 ,0]
dy = [0, 0, -1, 1]
def bfs(i,j):
	cnt = 1
	q = deque()
    # 여기서 넣어주면서 시작
	q.append((i, j))
    # 방문 처리 
	visited[i][j] = True
	while q:
		x, y = q.popleft()
		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 visited[nx][ny]: continue
            		# 0이면 방문 처리하고 숫자 증가  
			if graph[nx][ny] == 0 :
				visited[nx][ny] = True
				q.append((nx, ny))
                #이게 dfs 각 요소 더하는 것과 같은 역할 
				cnt += 1
	return cnt
for i in range(n):
	for j in range(m):
    		#여기서 방문 처리 리셋
		visited = [[False] * m for _ in range(n)]
		if graph[i][j] == 1:
        		#벽이면 bfs돌리자~
			answer[i][j] = bfs(i, j)
		else:
        		#벽이 아니면 그대로 출력
			answer[i][j] = 0
		print(answer[i][j], end='')
	print()

3번 풀이 (메모리 초과)

import sys
input  = sys.stdin.readline
sys.setrecursionlimit(100000)
n, m = map(int, input().split())
graph = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def dfs(x, y):
	global each
	if x < 0 or y < 0 or x >= n or y >= m:
		return False
	if graph[x][y] == 0 and not visited[x][y]:
		visited[x][y] = True
		pan[x][y] = tmp
		dfs(x-1, y)
		dfs(x+1, y)
		dfs(x, y+1)
		dfs(x, y-1)
		each += 1
		return True
	return False
info = {}
cnt = 0
tmp = 1
visited = [[False] * m for _ in range(n)]
pan = [[0]*m for _ in range(n)]
for i in range(n):
	for j in range(m):
		each = 0
		if dfs(i, j) == True:
			cnt += 1
			tmp += 1
			info[cnt] = each
def countMoves(x, y):
	candidates = set()
	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 not pan[nx][ny]: continue
		candidates.add(pan[nx][ny])
	cnt = 1
	for c in candidates:
		cnt += info[c]
		cnt = cnt % 10
	return cnt
answer = [[0]*m for _ in range(n)]
for i in range(n):
	for j in range(m):
		if graph[i][j] == 1:
			answer[i][j] = countMoves(i, j)
for i in range(n):
	for j in range(m):
		print(answer[i][j], end = '')
	print()

4번풀이(통과)

import sys
from collections import deque
input  = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def BFS(x, y):
	dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
	q = deque()
	q.append([x, y])
	visited[x][y] = 1
	cnt = 1
	while q:
		current_x, current_y = q.pop()
        	# zeros -> 그룹배열 만들기 
		zeros[current_x][current_y] = group
		for dx, dy in dir:
			next_x, next_y = current_x + dx, current_y + dy
			if next_x < 0 or next_y < 0 or next_x >= n or next_y >= m: continue
			if visited[next_x][next_y]: continue
			if not graph[next_x][next_y]:
				q.append([next_x, next_y])
				visited[next_x][next_y] = 1
                		#BFS를 DFS 처럼 
				cnt += 1
	return cnt
# 얼마나 이동할 수 있는지, 이동 할 수 있으면 그룹함수의 값을 더함
def countMoves(x, y):
	candidates = set()
	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 not zeros[nx][ny]: continue
		candidates.add(zeros[nx][ny])
	cnt = 1
	for c in candidates:
		cnt += info[c]
        	#답에서 10을 나눈 나머지 출력
		cnt = cnt % 10
	return cnt
#그룹마다 갯수 몇개인지 확인(인접해있는 0이 몇개인가?) 
info = {}
group = 1
#방문 체크
visited = [[0 for _ in range(m)] for _ in range(n)]
#그룹 배열
zeros = [[0 for _ in range(m)] for _ in range(n)]
for i in range(n):
	for j in range(m):
		if not graph[i][j] and not visited[i][j]:
			cnt = BFS(i, j)
			info[group] = cnt
			group += 1
answer = [[0 for _ in range(m)] for _ in range(n)]
for i in range(n):
	for j in range(m):
		if graph[i][j]:
			answer[i][j] = countMoves(i, j)
for i in range(n):
	print(''.join(map(str, answer[i])))

어렵고 힘들었지만 좋은 문제라고 기억할게 ㅋㅋ