[브루트포스] - 마인크래프트, 안전영역, 보물섬

18111번 _ 마인크래프트 문제

N, M ,B = list(map(int,s.readline().split()))

array = [list(map(int,s.readline().split())) for _ in range(N)]


listMax = max(map(max,array))
listMin = min(map(min,array))

result = int(1e9)
resultH = 0

for k in range(listMin,listMax+1):
    ans = 0
    block = B

    for i in range(N):
        for j in range(M):
            if array[i][j] > k :
                ans +=(array[i][j] - k) * 2
                block += 1
            else:
                ans +=abs(array[i][j] - k) * 1
                block -= 1

    if block < 0 :
        continue
    if result > ans:
        result = ans
        resultH = k

print(result, resultH)

이렇게 3중 for문을 돌리니까 시간초과가 떠서 다른 방법을 찾아야했다. 결국 시간 초과를 줄이는 방법은 For문을 줄이는 방법이 제일 효율적이기 때문에 for문을 하나 줄여야 했고 갯수를 list에 넣어서 한번에 계산하는 방식으로 해결했다.

N, M ,B = list(map(int,s.readline().split()))

array = [list(map(int,s.readline().split())) for _ in range(N)]

listMax = max(map(max,array))
listMin = min(map(min,array))

height_cnt = [0 for _ in range(listMax+1)]

for i in array:
    for j in i:
        height_cnt[j] += 1

result = int(1e9)
resultH = 0

for k in range(listMin,listMax+1):
    ans = 0
    block = B

    for i in range(listMax+1):
        if i < k:
            ans = ans+ (k-i)*height_cnt[i]
            block -= height_cnt[i] * abs(k - i)
        elif i > k:
            ans = ans + (i-k)*height_cnt[i]*2
            block += height_cnt[i] * abs(k-i)


    if block < 0 :
        continue
    if result >= ans and  resultH <= k:
        result = ans
        resultH = k

print(result, resultH)

실수한 부분

- 1 1 0
- 0        과 같은 예시일 때 resultH <= k 일때를 고려 안해서 틀림
- 같은 시간이면 더 높은 곳일 때를 출력해야되는데, 그 부분을 고려안함

안전 영역 - DFS

from sys import stdin as s
import sys
sys.setrecursionlimit(100000)

s = open('input.txt','rt')


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

n = int(s.readline())

array = [list(map(int, s.readline().split())) for _ in range(n)]



def dfs(x,y,depth):
    for i in range(4):
        if 0 <= x+dx[i] < n and 0 <= y+dy[i] < n  and array[x+dx[i]][y+dy[i]] > depth and visited[x+dx[i]][y+dy[i]]:
            visited[x+dx[i]][y+dy[i]] = False
            dfs(x+dx[i], y+dy[i], depth)


result =0

print(max(map(max,array)))
for k in range(max(map(max, array))):
    visited = [[True] * n for _ in range(n)]
    ans =0
    for i in range(n):
        for j in range(n):
            if visited[i][j] == True and array[i][j] > k:
                ans+=1
                visited[i][j] = False
                dfs(i,j,k)

        result = max(ans,result)

print(result)

안전 영역 - bfs

from sys import stdin as s
import sys
from collections import deque
sys.setrecursionlimit(100000)

s = open('input.txt','rt')


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

n = int(s.readline())

array = [list(map(int, s.readline().split())) for _ in range(n)]

result =0

def bfs(x,y,depth):
    queue = deque()
    queue.append((x,y))
    visited[x][y]= True
    while queue:
        hx,hy= queue.popleft()
        for i in range(4):
            nx = hx + dx[i]
            ny = hy + dy[i]
            if 0 <= nx < n and 0<= ny < n and array[nx][ny] > depth and not visited[nx][ny]:
                queue.append((nx,ny))
                visited[nx][ny] = True





#for i in range(max(map(max,array))):
for k in range(max(map(max,array))):
    visited = [[False] * n for _ in range(n)]
    ans =0
    for i in range(n):
        for j in range(n):  
            if not visited[i][j] and array[i][j] > k:
                ans +=1
                bfs(i,j,k)

    result =max(result,ans)


print(result)

보물섬

from sys import stdin as s
from collections import deque
import copy

s = open('input.txt','rt')

N, M = list(map(int,s.readline().split()))

array = [list(map(str,s.readline().rstrip())) for _ in range(N)]

dx = [0,-1,0,1]
dy = [1,0,-1,0]
global result
result =0
def bfs(x,y):
    global result
    maps = [item[:] for item in array]
    h = 0
    q = deque()
    q.append((x,y,h))
    maps[x][y] = 'W'
    ans = 0
    while q:
        hx ,hy,hh = q.popleft()
        ans = max(ans,hh)
        for i in range(4):
            nx = hx + dx[i]
            ny = hy + dy[i]
            nh = hh
            if 0 <= nx < N and 0 <= ny < M and maps[nx][ny] != 'W':
                maps[nx][ny] = 'W'
                q.append((nx,ny,nh+1))


    return ans

for i in range(N):
    for j in range(M):
        if array[i][j] == "L":
            if i> 0 and i+1<N and array[i-1][j] == "L" and array[i+1][j] =="L":
                continue
            if j> 0 and j+1<M and array[i][j-1] == "L" and array[i][j+1] =="L":
                continue
            result = max(result,bfs(i,j))


print(result)

처음에 로직대로 L인 육지에서 시작해서 방향마다 bfs로 탐색해서 최단거리를 찾아줘서 풀었는데 57%쯤 채점하고 계속 시간초과가 발생했다.

- 실수한 부분
- 탐색 시작하고자 하는 곳이 가장자리가 아닐때는 최단거리가 될 수 없기 때문에 해당하는 부분을 제외하고 검사하면 시간초과가 나지 않는다.
- W L L
- L L L
- W W L
- 이런 지도라 생각했을 때 (1,1)은 좌우로 L이기 때문에 탐색 시작지점으로 적합하지 않다.

브루트 포스 문제는 중요한 것 같아서 dfs, bfs 둘 다 풀어 보았고, 앞으로 한참은 브루트 포스 문제를 중점으로 풀어야 될 것 같다.

브루트 포스 문제 리스트

NO	LV	유형	제목	비고
18111	S2	브루트 포스	마인 크래프트	첫 시도 시간초과
14889	S2	브루트 포스	스타트와 링크	완전 탐색으로 6개 중에 3개를 조합하고 싶다면 dfs탈출 조건을 n//2로 주면 된다
2468	S1	브루트 포스	안전 영역	dfs, bfs모두 풀어봄
2589	G5	브루트 포스	보물섬	첫 번째 시간 초과, 예외처리 해주니 통과
1018	S4	브루트 포스	체스판 다시 칠하기	for문 4개 돌리면 되는데 괜히 bfs로 하려다가 시간 잡아먹음