[백준] 1046 그림자 Python 3

문제 접근 방식

1. 방의 구조를 입력받고, 광원의 위치와 벽의 개수를 파악합니다.
2. 광원으로부터 빛이 퍼지는 영역을 계산합니다. 이때 빛이 벽에 의해 차단되는 경우를 고려합니다.
3. 각 방향(상하좌우)으로 빛이 퍼져나가며, 빛이 닿는 영역을 계산합니다.
4. 최종적으로 빛이 닿는 영역의 총 면적을 계산하여 빈 공간에 대한 비율을 출력합니다.

각 함수의 역할 및 설명

1. get_triangle_area 함수

이 함수는 주어진 삼각형의 면적을 계산합니다. 삼각형의 세 점 중 두 점이 x축 위에 있을 때, 삼각형의 밑변과 높이를 이용해 면적을 계산합니다. 이 함수는 빛이 벽에 의해 차단되는 경우 삼각형 면적을 빼기 위해 사용됩니다.

2. get_light_area_and_next 함수

이 함수는 현재 y 좌표에서 빛이 비추는 영역과 다음 y 좌표에서의 빛 영역을 계산합니다. 빛이 벽에 의해 차단되는지 여부를 판단하고, 차단된 경우 삼각형 면적을 빼줍니다.

3. get_wall_coords 함수

이 함수는 주어진 offset에 대해 벽의 좌표를 생성합니다. 특정 y 좌표에서의 벽 좌표를 계산하는 데 사용됩니다.

4. get_wall 함수

이 함수는 특정 좌표에 벽이 있는지 확인합니다. 방의 경계를 벗어나면 항상 벽으로 간주합니다.

5. get_light_area 함수

이 함수는 광원이 비추는 전체 영역의 면적을 계산합니다. 네 방향(상하좌우)으로 빛이 퍼져나가며 벽에 의해 차단되는 경우를 고려합니다.

 

from fractions import Fraction as F

# 입력 값을 받아들임
N, M = map(int, input().split())  # N: 행 수, M: 열 수
lx, ly = -1, -1  # 광원의 초기 위치

room = []
wall_count = 0  # 벽의 개수를 세기 위한 변수

# 방의 각 행을 입력받고 처리함
for y in range(N):
    row = input()
    room.append(row)
    for x in range(M):
        if row[x] == '*':  # 광원의 위치를 찾음
            assert(lx < 0 and ly < 0)
            lx, ly = x, y
        elif row[x] == '#':  # 벽의 개수를 셈
            wall_count += 1
        else:
            assert(row[x] == '.')  # 나머지는 빈 공간

# 삼각형의 면적을 계산하는 함수
def get_triangle_area(x_top, x_bottom, x_target):
    len_base = (x_bottom - x_target) if x_target < x_bottom else (x_target - x_bottom)
    len_height = (x_bottom - x_target) / (x_bottom - x_top)
    return len_base * len_height / 2

# 주어진 y 좌표에서 빛이 비추는 영역과 다음 y 좌표에서의 빛 영역을 계산하는 함수
def get_light_area_and_next(dy, curr_lights, walls):
    light_area = F(0)  # 빛이 비추는 영역의 면적
    next_lights = []  # 다음 y 좌표에서의 빛 영역

    curr_light_ind = 0
    light_mult = (dy+1)/dy

    prev_block = True
    next_block = False
    for i in range(len(walls)):
        if curr_light_ind >= len(curr_lights):
            break
        if i == len(walls)-1: next_block = True
        else: next_block = walls[i+1]
        if not walls[i]:
            x_center = F(i - len(walls)//2)
            x_left = x_center - F(1, 2)
            x_right = x_center + F(1, 2)
            for li in range(curr_light_ind, len(curr_lights)):
                light_l, light_r = curr_lights[li]

                if light_r <= x_left:
                    curr_light_ind = li+1
                    continue

                if light_l >= x_right:
                    break

                if light_l < x_left: light_l = x_left
                if light_r > x_right: light_r = x_right

                if light_l >= light_r:
                    continue
                
                light_dl, light_dr = light_mult*light_l, light_mult*light_r

                curr_area = (light_r - light_l + light_dr - light_dl) / 2
                
                if prev_block and light_dl < x_left:
                    curr_area -= get_triangle_area(light_l, light_dl, x_left)
                    if light_dr < x_left:
                        curr_area += get_triangle_area(light_r, light_dr, x_left)
                if next_block and light_dr > x_right:
                    curr_area -= get_triangle_area(light_r, light_dr, x_right)
                    if light_dl > x_right:
                        curr_area += get_triangle_area(light_l, light_dl, x_right)

                light_area += curr_area

                if light_dl < x_left and prev_block: light_dl = x_left
                if light_dr > x_right and next_block: light_dr = x_right
                if light_dl < light_dr:
                    if len(next_lights) > 0 and next_lights[-1][1] == light_dl:
                        next_lights[-1][1] = light_dr
                    else:
                        next_lights.append([light_dl, light_dr])
        prev_block = walls[i]
    
    return (light_area, next_lights)

# 주어진 offset에 대해 벽의 좌표를 생성하는 함수
def get_wall_coords(lx, ly, dx, dy, offset):
    for i in range(-offset, offset+1):
        yield (lx + dx*offset + dy*i, ly + dy*offset + dx*i)

# 특정 좌표에 벽이 있는지 확인하는 함수
def get_wall(x, y):
    if 0 <= x < M and 0 <= y < N: return room[y][x] == '#'
    else: return True

# 전체 빛 영역의 면적을 계산하는 함수
def get_light_area(room, lx, ly):
    total = F(1)  # 광원이 위치한 초기 영역
    for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        curr_lights = [(F(-1, 2), F(1, 2))]
        offset = 1
        while True:
            walls = [get_wall(x, y) for (x, y) in get_wall_coords(lx, ly, dx, dy, offset)]
            if all(walls): break
            curr_area, next_lights = get_light_area_and_next(F(2*offset-1, 2), curr_lights, walls)
            total += curr_area
            offset += 1
            curr_lights = [(l, r) for (l, r) in next_lights if l < r]
            if len(curr_lights) == 0: break
        
    return total

# 광원이 비추는 영역을 계산하여 벽을 제외한 영역의 넓이를 계산
num, den = round(N*M - wall_count - get_light_area(room, lx, ly), ndigits=12).as_integer_ratio()
print(num/den)

문제 해결 과정

1. 입력 및 초기화:
   • 첫 번째 줄에서 방의 크기 N과 M을 입력받습니다.
   • 방의 각 행을 입력받아 room 리스트에 저장하고, 광원의 위치를 찾습니다. 벽의 개수를 세어 wall_count 변수에 저장합니다.
2. 삼각형의 면적 계산:
   • get_triangle_area 함수는 주어진 삼각형의 면적을 계산합니다. 이 함수는 빛이 벽에 의해 차단될 때, 차단된 부분을 빼기 위해 사용됩니다.
3. 빛 영역 계산:
   • get_light_area_and_next 함수는 현재 y 좌표에서 빛이 비추는 영역과 다음 y 좌표에서의 빛 영역을 계산합니다. 이 함수는 빛이 벽에 의해 차단되는지 여부를 판단하고, 차단된 경우 삼각형 면적을 빼줍니다.
4. 벽 좌표 생성:
   • get_wall_coords 함수는 주어진 offset에 대해 벽의 좌표를 생성합니다. 이 함수는 특정 y 좌표에서의 벽 좌표를 계산하는 데 사용됩니다.
5. 벽 확인:
   • get_wall 함수는 특정 좌표에 벽이 있는지 확인합니다. 이 함수는 방의 경계를 벗어나면 항상 벽으로 간주합니다.
6. 전체 빛 영역 계산:
   • get_light_area 함수는 광원이 비추는 전체 영역의 면적을 계산합니다. 이 함수는 네 방향(상하좌우)으로 빛이 퍼져나가며 벽에 의해 차단되는 경우를 고려합니다.
7. 최종 계산 및 출력:
   • 빛이 비추는 전체 영역의 넓이를 계산하고, 벽으로 차단된 영역을 제외하여 최종적으로 빈 공간에 비추는 빛의 비율을 계산하여 출력합니다.

이 코드를 통해 방 안에서 광원이 비추는 영역의 넓이를 정확하게 계산할 수 있습니다. 빛이 퍼지는 과정을 단계별로 구현하여, 벽에 의해 차단되는 경우를 고려한 결과를 얻을 수 있습니다.