글 읽기 - 최적화에 대한 조건 질문.

lwh1992 4년 전 0

~~예제와 다른 예시를 직접 넣어봤는데 뭐가 틀린지 모르겠어서 질문드립니다.~~

~~맵의 값이 'L' 일때 주변탐색후 L의 개수가 2개 이상이면 건너뛰는 식으로 했습니다.~~

주변 개수를 COUNT 할때 2개 이상이 아닌 더 세부적인 조건으로 해야한다는 것을 알았습니다..

이럴 경우에 직선을 조건으로 하는데, 그게 최적이라는 전제를 어떻게 얻을 수 있는지 궁금합니다.

from collections import deque

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


def bfs(_x, _y):
    Q = deque()
    Q.append([_x,_y])
    check_arr[_x][_y] = 0
    ans = 0
    while Q:
        x, y = Q.popleft()
        step = check_arr[x][y]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n and \
                    check_arr[nx][ny] == -1 and arr[nx][ny] == 'L':
                check_arr[nx][ny] = step + 1
                if ans<step + 1:
                    ans = step+1
                Q.append([nx, ny])
    # print(*check_arr, sep='\n')
    # print()
    return ans


m, n = map(int, input().split())
arr = [list(input()) for _ in range(m)]
result = 0
for x in range(m):
    for y in range(n):
        if arr[x][y] == 'L':
            count = 0
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < m and 0 <= ny < n and arr[nx][ny] == 'L':
                    count += 1
                    # 주변 L의 개수를 COUNT
            if count >= 2: continue
                # 2값을 3으로 바꿨습니다.
            check_arr = [[-1] * n for _ in range(m)]
            # -1인 부분만 탐색하고 탐색한 부분은 0부터 거리값을 대입
            tmp = bfs(x, y)
            if tmp>result:
                result = tmp
print(result)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

최적화에 대한 조건 질문.

lwh1992 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말