본문 바로가기
Algorithm/구현

[Python3] 백준 1347번 미로 만들기

by HANNI하니 2023. 4. 9.

사용 언어 - Python3

문제 - 미로 만들기

 

1347번: 미로 만들기

홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍

www.acmicpc.net

 

정답

최대 x,y 값 구하고, 2차원 배열 만들기 (정답 맞춘 여부 X)

1. loc_list (0,0)에서 시작해서 이동한 값 x,y에 저장하기

R 명령어) 방향을 오른쪽으로 전환 -> status+1 한 후 4로 나누어 몇번째 원소인지 찾기 (status+1)%4

L 명령어) 방향을 왼쪽으로 전환 -> status가 0이 아니라면, status-1, 아니면 3

x는 loc_list의 가장 최근 x좌표에서 R명령어를 통해 전환된 dx를 더한다.

y는 loc_list의 가장 최근 y좌표에서 L명령어를 통해 전환된 dy를 더한다.

loc_list에 현재의 (x,y)를 append해준다.

 

2. x와 y의 최대 최소값 구해서 미로 배열 만들기

loc_list를 x[0] (0,0)을 기준으로 정렬해 최소값과 최대값을 구한다.

 

3. 혹시 음수가 생길 수도 있으니 각 loc_list 원소에서 최소값을 빼준다

4. loc_list가 있는 위치에 "." 붙여주기

5. print("".join(row))

import sys

input = sys.stdin.readline

N = int(input())
action = input().strip()

loc_list = [(0, 0)] 
dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]
status = 2
for a in action:
    if a == 'R':
        status = (status + 1) % 4
    elif a == 'L':
        status = (status - 1) if status != 0 else 3
    else:
        x = loc_list[-1][0] + dx[status]
        y = loc_list[-1][1] + dy[status]
        loc_list.append((x, y))
        
x_sort = sorted(loc_list, key=lambda x: x[0])
y_sort = sorted(loc_list, key=lambda x: x[1])
x_min, x_max = x_sort[0][0], x_sort[-1][0]
y_min, y_max = y_sort[0][1], y_sort[-1][1]

maze = [['#' for y in range(y_min, y_max + 1)] for x in range(x_min, x_max + 1)]

for i in range(len(loc_list)):
    loc_list[i] = (loc_list[i][0] - x_min, loc_list[i][1] - y_min)

for i, j in loc_list:
    maze[i][j] = '.'

for row in maze:
    print(''.join(row))

 

 

 


레퍼런스

  • 정답 참고
 

[python] 백준 - 1347. 미로 만들기

🤔문제 해결 구현 좌표를 먼저 구하자. (0, 0) 에서 시작해서 제시된 행동대로 좌표로 담아준다. x좌표, y좌표 각각의 최소와 최대를 구한다. 모든 좌표들에 대해서 최소값을 더해준다. ( 음수가

deok2kim.tistory.com

  • 정답 깃허브
 

GitHub - yyeongeun/codingtest: 코딩테스트 공부

코딩테스트 공부. Contribute to yyeongeun/codingtest development by creating an account on GitHub.

github.com

 

댓글