[python] 백준 1730. 판화

문제

https://www.acmicpc.net/problem/1730

W대학교 미술대학 조소과에서는 지루한 목판화 작업을 하는 학생들을 돕기 위해 판화 기계를 제작하였다.

기계는 로봇 팔이 쥔 조각도를 상하좌우 네 방향으로 움직일 수 있는 구조로서, 조각도 아래에 목판을 놓으면 그 위에 선들을 자동으로 그어주는 기능을 가지고 있다.

목판에는 N2개의 점들이 일정한 간격으로 N행 N열의 격자모양을 이루며 찍혀있다. 처음 로봇의 조각도를 올려놓는 위치는 항상 이 점들 중 맨 왼쪽 맨 위의 꼭짓점이다.

로봇 팔을 움직이는 명령의 순서가 주어졌을 때, 목판 위에 패인 조각도의 혼적을 출력하는 프로그램을 작성하시오.

판화 기계는 작동 도중 로봇 팔이 격자 바깥으로 나가도록 하는 움직임 명령을 만나면, 무시하고 그 다음 명령을 진행한다.

입력

첫째 줄에 목판의 크기 N (2 ≤ N ≤ 10)이 주어진다. 행 열의 점들이 찍혀 있다는 의미이다. 둘째 줄에 로봇팔의 움직임이 한 줄로 공백 없이 입력된다. 위쪽으로 이동은 'U', 아래쪽으로 이동은 'D', 왼쪽으로 이동은 'L', 오른쪽으로 이동은 'R'로 표시된다. 로봇팔의 움직임을 나타내는 이 문자열의 길이는 최대 250이다.

출력

로봇팔이 지나지 않은 점은 '.'으로, 로봇팔이 수직 방향으로만 지난 점은 '|'으로, 로봇팔이 수평 방향으로만 지난 점은 '-'으로, 수직과 수평 방향 모두로 지난 점은 '+'로 표기하도록 한다. 네 문자의 ASCII 코드는 각각 46, 124, 45, 43이다.

---

풀이

처음에 다 구현을 한 채로 코드를 짰었는데 계속 틀렸다고 해서 다시 풀기 너무너무 어려웠다...

https://ehddud100677.tistory.com/255

백준 1730번 파이썬

중간에 헤매다가 위 사이트 코드를 참고해서 힌트를 얻었다!

import sys
input = sys.stdin.readline

n = int(input().strip()) 
data = [['.'] * n for _ in range(n)] 
message = input().strip() 
x, y = 0, 0 

for m in message:
    if m == 'D':  # 아래로 이동
        if x + 1 < n: 
            for j in range(2):
                if data[x][y] == '-':
                    data[x][y] ='+'
                elif data[x][y] == '.':
                    data[x][y] = '|'
                if j == 0:
                    x += 1
                    
    elif m == 'U':  # 위로 이동
        if x - 1 >= 0: 
            for j in range(2):
                if data[x][y] == '-':
                    data[x][y] ='+'
                elif data[x][y] == '.':
                    data[x][y] = '|'
                if j == 0:
                    x -= 1
    elif m == 'L':  # 왼쪽으로 이동
        if y - 1 >= 0:  
            for j in range(2):
                if data[x][y] == '|':
                    data[x][y] ='+'
                elif data[x][y] == '.':
                    data[x][y] = '-'
                if j == 0:
                    y -= 1
    elif m == 'R':  # 오른쪽으로 이동
        if y + 1 < n: 
            for j in range(2):
                if data[x][y] == '|':
                    data[x][y] ='+'
                elif data[x][y] == '.':
                    data[x][y] = '-'
                if j == 0:
                    y += 1
    
for row in data:
    print(''.join(row))

 

이 문제는 사실 

for j in range(2):
                if data[x][y] == '-':
                    data[x][y] ='+'
                elif data[x][y] == '.':
                    data[x][y] = '|'
                if j == 0:
                    x += 1

이 부분만 잘 이해하면 다 풀 수 있는 문제였는데, 왜 2번을 반복하냐면...

이런 식으로 결과적으로는 두 칸씩 내용이 저장되는 것을 예제를 통해 이해할 수 있다. (왜 그런지는 사실 잘 모르겠다. 왜 이렇지?)

근데 일단 예제가 이렇다보니... 이렇게 코드를 짜야하고 그렇기 때문에 2번 반복해서 이동하기 전에 위치를 한번 확인해서

1. .인지 반대인지 확인하고

2. 만약에 같은 거면 냅두고

3. 반대면 바꿔준다. (+)로,

4. .이면 자기꺼를 넣어주고

명령에 맞춰 이동해서 거기서도 위 같은 과정을 한번 더 거치면 되는 문제였다. 

 

저 if문은 그냥 범위를 벗어났는지 확인하려고 넣은 거다.

 

시간복잡도

시간복잡도는... 배열에 맞게 입력 받고 출력하는 걸로 O(n^2)이 걸리고... 명령에 맞게 반복하는 거 for문은 O(m)일 것 같다. 그래서 O(n^2+m) 일 것 같다...