-
풀이과정
이전에 만들어 놓았던 탐색 알고리즘을 통해 입력으로 들어오는 데이터로 미로를 만들어주었다. 우선 인풋데이터를 이용해 MAP을 그려주고, (0,0)을 시작으로 탐색을 시작하는데 지금 돌고있는 i가 만약 0이라면 멈추고 1이라면 진행한다 이때, 4방향을 검사하기 위해 DX와 DY를 좌표에 맞게 +1,-1, 0 을 적절하게 배열에 담아준다 담고 진행 할 때마다 Count를 체크해 도착점에 도달한 cnt를 queue 적재해준다 최소한으로 칸을 밟은 데이터를 queue에서 찾고 답을 print한다 -
Sol
n, m = map(int, input().split())
s = []
queue = []
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(n):
s.append(list(input()))
queue = [[0, 0]]
s[0][0] = 1
while queue:
a, b = queue[0][0], queue[0][1]
# ab에는 큐에 담긴 좌표를 기반으로 디큐
del queue[0]
for i in range(4):
x = a + dx[i]
y = b + dy[i]
if 0 <= x < n and 0 <= y < m and s[x][y] == "1":
queue.append([x, y])
s[x][y] = s[a][b] + 1
# 만약 돌고잇는게 0보다적거나 1이라면 다음 데이터셋으로
print(s[n - 1][m - 1])
-
풀이과정
까다로운 문제다, BFS나 백트래킹을 동시에 요구한다.
n*m크기의 MAP을 그려주고, 들어오는 값에 맞춰 2(바이러스)가 4방향으로 퍼질 때, 1(벽)이 존재한다면 2는 벽이 존재 하지 않는 곳으로 이동해야한다.
안전 영역= 2번이 지나갈 수 없는 곳을 뜻하는데 결과적으로 벽을 추가적으로 (3개)를 세워 안전영역을 가장 크게 만들어야한다
고로 들어온 1을 통해 2번을 기준으로 가장많은 0번의 묶음을 만들어야하는데,
시간초과 이슈가 있다 그래서 pypy3으로한번, python으로 한번 풀었다.
이전과 같이 map을 그려주고 입력 받는 빈칸의 좌표를 list에 담아두고, 삼중 for문을 통해 3개의 벽을 세우고 바이러스를 퍼트린다 = BFS
BFS탐색으로 연산이 완료되면 벽을 없애준다.
고로 빈칸에 3개의 벽을 세우고, 바이러스가 경로탐색을 통해 2번을 전파하고 종료되면 벽을 허물고 다시 다른위치에 벽을두고 탐색을 시작하여 가장 큰 안전 영역을 만드는 방법을 찾는다
-
Sol (1번방법)
import collections
import copy
import sys
n, m = map(int, sys.stdin.readline().split())
max_num = 0
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
empty_list = []
virus_list = []
EMPTY = 0
WALL = 1
VIRUS = 2 # 입력
g = [[0] * m for _ in range(n)]
for y in range(n):
raw = [int(x) for x in sys.stdin.readline().split()]
for x in range(m):
g[y][x] = raw[x]
if g[y][x] == EMPTY:
empty_list.append([y, x])
if g[y][x] == VIRUS:
virus_list.append([y, x])
# bfs 탐색
def bfs(ng):
q = collections.deque([])
visited = [[False] * m for _ in range(n)]
cnt = 0
global max_num
for virus in virus_list:
q.append(virus)
while q:
cy, cx = q.popleft()
for i in range(4):
ny = cy + dy[i]
nx = cx + dx[i]
if ny < 0 or ny >= n or nx < 0 or nx >= m:
continue
if ng[ny][nx] == EMPTY and visited[ny][nx] == False:
q.append([ny, nx])
ng[ny][nx] = VIRUS
visited[ny][nx] = True
for i in range(n):
cnt += ng[i].count(EMPTY)
if max_num < cnt:
max_num = cnt
for i in range(len(empty_list)):
for j in range(i):
for k in range(j):
y1, x1 = empty_list[i]
y2, x2 = empty_list[j]
y3, x3 = empty_list[k]
g[y1][x1] = WALL
g[y2][x2] = WALL
g[y3][x3] = WALL
ng = copy.deepcopy(g)
bfs(ng)
g[y1][x1] = EMPTY
g[y2][x2] = EMPTY
g[y3][x3] = EMPTY
print(max_num)
(2번방법)
from collections import deque
import copy
def BFS():
queue = deque()
tmp_graph = copy.deepcopy(graph)
for i in range(n):
for j in range(m):
if tmp_graph[i][j] == 2:
queue.append((i, j))
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 tmp_graph[nx][ny] == 0:
tmp_graph[nx][ny] = 2
queue.append((nx, ny))
global answer
cnt = 0
for i in range(n):
cnt += tmp_graph[i].count(0)
answer = max(answer, cnt)
def makeWall(cnt):
if cnt == 3:
BFS()
return
for i in range(n):
for j in range(m):
if graph[i][j] == 0:
graph[i][j] = 1
makeWall(cnt + 1)
graph[i][j] = 0
n, m = map(int, input().split())
graph = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
for i in range(n):
graph.append(list(list(map(int, input().split()))))
answer = 0
makeWall(0)
print(answer)
pypy3으로 제출해야함..