SW Expert Academy 1824. 혁진이의 프로그램 검증

문제에서는 혁진이가 만든 혁어셈블리어를 이용해 만든 프로그램을 검증하는 함수를 구현해야 한다.

수행 명령에 따라 2차원 배열을 이동하면서 프로그램이 실행을 정지하는 '@'문제에 도달할 수 있는지 알아보자

삼성 SW Expert Academy에서 푼 문제 리스트 보기

github에서 코드 보기

문제 조건

혁진이가 만든 명령어에 따라 명령을 수행한다.

만약 다음 이동이 2차원 격자의 바깥으로 이동하는 방향이라면, 반대편에 있는 위치로 이동한다.

혁셈블리어에는 메모리가 단 하나 있으며, 0에서 15사이의 정수를 하나 저장할 수 있다.

가장 처음에는 0이 저장되어 있으며 오른쪽으로 먼저 이동한다.

문자	수행 명령
<	이동 방향을 왼쪽으로 바꾼다.
>	이동 방향을 오른쪽으로 바꾼다.
^	이동 방향을 위쪽으로 바꾼다.
v	이동 방향을 아래쪽으로 바꾼다.
_	메모리에 0이 저장되어 있으면 이동 방향을 오른쪽으로 바꾸고, 아니면 왼쪽으로 바꾼다.
\|	메모리에 0이 저장되어 있으면 이동 방향을 아래쪽으로 바꾸고, 아니면 위쪽으로 바꾼다.
?	이동 방향을 상하좌우 중 하나로 무작위로 바꾼다. 방향이 바뀔 확률은 네 방향 동일하다.
.	아무 것도 하지 않는다.
@	프로그램의 실행을 정지한다.
0~9	메모리에 문자가 나타나는 값을 저장한다.
+	메모리에 저장된 값에 1을 더한다. 만약 더하기 전 값이 15라면 0으로 바꾼다.
-	메모리에 저장된 값에 1을 뺀다. 만약 빼기 전 값이 0이라면 15로 바꾼다.

문제 풀이

다른 명령어를 처리하는 건 어렵지 않다. "?"만 재귀로 잘 처리해주면 된다.

1) 원소(내 코드에선, pos)에 도달하면 명령어에 따라서 숫자와 다음 갈 방향, 다음 갈 원소(pos)의 위치를 알아낸다.

2) 다음 원소의 위치가 2차원 배열을 넘어서게 된다면 문제의 조건에 따라서 반대편 위치로 이동시킨다.

3) 검증 코드가 무한 루프에 빠지는 것을 방지하기 위해서 방문을 표시한다. visited 2차원 배열을 만들고 방문 당시의 (방향 정보, 숫자 정보)를 배열을 만들어 넣어준다.

4) 나중에 다시 이 지점을 방문했을 때,visited의 배열에 담은 정보를 꺼내와 똑같은 (방향, 숫자 정보) 방문정보를 가지고 있다면, 무한 루프에 빠진 것으로 생각할 수 있다.

5) @를 만났을 경우에는 True를 리턴해주고 그렇지 않은 경우에는 아무것도 리턴해주지 않는다. 모든 탐색을 마치고 True를 리턴했을 때에만 'YES'로 표시한다.

문제를 틀렸다면 주의할 사항

1) "YES', "NO" 모두 대문자다.

2) 방문 여부를 처리할 때 숫자 값만 비교하면 안되고, 방향값도 비교해주어야 한다. 왼쪽에서 접근해 방문한 거랑, 오른쪽에서 접근해 방문한거랑 완전 다른거.

3) '?' 문자의 경우에는 재귀를 호출하여 4가지 방향을 모두 탐색해주어야 한다. (왔던 길이라고 그거 빼고 탐색하면 안된다는 말임)

4) 유일하게 프로그램을 종료할 수 있는 방법인 @ 문자가 2차원 배열에 존재하는지 체크해보았는지 확인한다.

5) 파이썬으로 풀게 될 경우, 아래의 경우에는 재귀 횟수 초과가 나서 에러가 난다. 내 코드가 잘 돌아가는지 확인이라도 하고 싶다면 sys 라이브러리를 확용해서 재귀 허용 횟수를 높여보면 된다. 그치만 SW Expert Academy에선 적절하지 않은 라이브러리라고 하기 때문에 사용할 수 없으므로 단순히 테스트 용이다. 아래 테스트 예제처럼 @ 주위를 회오리 바람처럼 감싸고 있는지를 확인해줌으로써 아래의 테스트 케이스를 통과할 수 있었다. 그치만 이건 테스트 케이스를 모두 알기 때문에 쓸 수 있었던 임시 방편이라서 코드가 만족스럽진 않다.

1
2
import sys
sys.setrecursionlimit(100000)
cs

20 20

????????????????????

??????????????????>?

?????????????????^@v

??????????????????<+

파이썬 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
# import sys
# sys.setrecursionlimit(100000)
 
def nextStep(array, visited, dir, num, pos):
    """
    :param dir: 다음으로 이동할 방향 ("<", ">", "v", "^")\
    :param visited: 방문 당시 정보 저장 (방문 당시 진행 방향, 숫자 정보)
    :param num: 현재의 숫자
    :param pos : 현재의 위치 (r,c)
    :return: (boolean) 도달 여부
    """
    while pos:
        letter = array[pos[0]][pos[1]]
 
        # @ : 프로그램의 실행 정지
        if letter == '@':
            return True
 
        # 동일한 방문 정보가 있다면 무한 반복이므로 종료
        if (dir, num) in visited[pos[0]][pos[1]]:
            return False
        visited[pos[0]][pos[1]].add((dir, num))
 
        # ?    이동 방향을 상하좌우 중 하나로 무작위로 바꾼다
        if letter == "?":
            # 방금 지나 왔던 길을 제외하고, 이동할 수 있는 모든 경우의 수를 생각한다.
            all = ["<", ">", "v", "^"]
            while all:
                nextdir = all.pop()
                if nextStep(array, visited, nextdir, num, nextPos(nextdir, pos)):
                    return True
        else:
            # 숫자 처리
            # 0~9    메모리에 문자가 나타내는 값을 저장한다.
            if letter.isdigit():
                num = int(letter)
 
            if letter in ["<", ">", "^", "v"]:
                dir = letter
 
            # _    : 메모리에 0이 저장되어 있으면 이동 방향을 오른쪽으로 바꾸고, 아니면 왼쪽으로 바꾼다.
            if letter == "_":
                if num == 0:
                    dir = ">"
                else:
                    dir = "<"
 
            # |    : 메모리에 0이 저장되어 있으면 이동 방향을 아래쪽으로 바꾸고, 아니면 위쪽으로 바꾼다.
            if letter == "|":
                if num == 0:
                    dir = "v"
                else:
                    dir = "^"
 
            # +    메모리에 저장된 값에 1을 더한다. 만약 더하기 전 값이 15이라면 0으로 바꾼다.
            if letter == "+":
                if num == 15:
                    num = 0
                else:
                    num += 1
 
            # -    메모리에 저장된 값에 1을 뺀다. 만약 빼기 전 값이 0이라면 15로 바꾼다.
            if letter == "-":
                if num == 0:
                    num = 15
                else:
                    num -= 1
            # 다음 방향이 유효한지 확인
            pos = nextPos(dir, pos)
 
# 다음 pos 정보 반환
def nextPos(dir, current_pos):
    direction = {"<": (0, -1), ">": (0, 1), "v": (1, 0), "^": (-1, 0)}
    r,c = current_pos
 
    tr, tc = direction[dir]
    temp_r = r + tr
    temp_c = c + tc
 
    # 범위 초과 시 조건에 따라 변경
    if temp_r < 0 or temp_c < 0 or temp_r >= n or temp_c >= m:
        if dir == "<":
            temp_c = m - 1
        elif dir == ">":
            temp_c = 0
        elif dir == "^":
            temp_r = n - 1
        elif dir == "v":
            temp_r = 0
    return (temp_r, temp_c)
 
 
def solve(array, visited):
    end = 0
    end_point = []
    for qi in range(n):
        for qv in range(m):
            if array[qi][qv] == '@':
                end += 1
                end_point.append((qi,qv))
    if end < 1:
        return "NO"
 
    for pos in end_point:
        r, c = pos
        top_and_bottom = [(-1, 0), (1,0)]
        left_and_right = [(0,1),(0,-1)]
        bad_count = 0
        # @에 접근 못하도록 방향 전환 문자가 둘러쌓았는지 확인
        for add in top_and_bottom:
            temp_r = r + add[0]
            temp_c = c + add[1]
            if 0 <= temp_r and 0 <= temp_c and temp_r < n and temp_c < m:
                if array[temp_r][temp_c] in ["<", ">"]:
                    bad_count += 1
                else:
                    bad_count = 0
                    break
 
        for add2 in left_and_right:
            temp_r = r + add2[0]
            temp_c = c + add2[1]
            if 0 <= temp_r and 0 <= temp_c and temp_r < n and temp_c < m:
                if array[temp_r][temp_c] in ["^", "v"]:
                    bad_count += 1
                else:
                    bad_count = 0
                    break
 
        # 4면이 접근 불가능하면 유효한 end_point 수 삭제
        if bad_count == 4:
            end -= 1
 
    # 접근 가능한 end_point가 있는지 확인
    if end < 1:
        return "NO"
 
    if nextStep(array, visited, '>', 0, (0,0)):
        return 'YES'
    else:
        return "NO"
 
if __name__ =="__main__":
    t = int(input())
    for i in range(t):
        array = []
        n, m = map(int, input().strip().split())
        for j in range(n):
            array.append(list(input().strip()))
 
 
        visited = []
        for vi in range(n):
            visit = []
            for ic in range(m):
                visit.append([])
            visited.append(visit)
        print("#{0} {1}".format(i+1, solve(array, visited)))
 
 
Colored by Color Scripter
cs

#혁진이의 프로그램 검증 #SW Expert Academy #1824. 혁진이의 프로그램 검증 #python 1824. 혁진이의 프로그램 검증 #1824. 혁진이의 프로그램 검증 python #파이썬 1824 혁진이의 프로그램 검증

저작자표시 비영리 변경금지

'온라인 코딩 테스트 문제 풀이 > 삼성 SW Expert 문제 풀이' 카테고리의 다른 글

Python으로 푸는 SW Expert Academy 1974. 스도쿠 검증 (0)	2019.02.28
Python으로 푸는 SW Expert Academy 1204. 최빈수 구하기 (0)	2019.02.27
Python으로 푸는 SW Expert Academy 1209. Sum (0)	2019.02.25
Python으로 푸는 SW Expert Academy 1868. 파핑파핑 지뢰찾기 (0)	2019.02.23

Daim's blog

Python으로 푸는 SW Expert Academy 1824. 혁진이의 프로그램 검증

SW Expert Academy 1824. 혁진이의 프로그램 검증

문제 조건

문제 풀이

문제를 틀렸다면 주의할 사항

파이썬 코드

#혁진이의 프로그램 검증 #SW Expert Academy #1824. 혁진이의 프로그램 검증 #python 1824. 혁진이의 프로그램 검증 #1824. 혁진이의 프로그램 검증 python #파이썬 1824 혁진이의 프로그램 검증

'온라인 코딩 테스트 문제 풀이 > 삼성 SW Expert 문제 풀이' 카테고리의 다른 글

티스토리툴바

« 2024/05 »
일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

SW Expert Academy 1824. 혁진이의 프로그램 검증

문제 조건

문제 풀이

문제를 틀렸다면 주의할 사항

파이썬 코드

#혁진이의 프로그램 검증 #SW Expert Academy #1824. 혁진이의 프로그램 검증 #python 1824. 혁진이의 프로그램 검증 #1824. 혁진이의 프로그램 검증 python #파이썬 1824 혁진이의 프로그램 검증

'온라인 코딩 테스트 문제 풀이 > 삼성 SW Expert 문제 풀이' 카테고리의 다른 글

검색

티스토리툴바