✔ 풀이를 위한 아이디어
- 그래프 이론 + 너비 우선 탐색
- 예외 케이스를 통한 오류 해결 + 논리적 사고력으로 케이스 분류
✔ 오답 코드 [틀렸습니다]
import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
Map = []
for _ in range(N):
Map.append(list(map(int, sys.stdin.readline().strip())))
queue = deque()
queue.append((0, 0))
count = 0
success = 0
visited = [[0]*M for _ in range(N)]
visited[0][0] = 1
chance = 1
while queue:
if success:
break
count += 1
for _ in range(len(queue)):
x, y = queue.popleft()
if x == M-1 and y == N-1:
success = 1
break
if x > 0:
if Map[y][x-1] == 0 and not visited[y][x-1]:
queue.append((x-1, y))
visited[y][x-1] = 1
elif chance and not visited[y][x-1]:
queue.append((x-1, y))
chance = 0
if x < M-1:
if Map[y][x+1] == 0 and not visited[y][x+1]:
queue.append((x+1, y))
visited[y][x+1] = 1
elif chance and not visited[y][x+1]:
queue.append((x+1, y))
chance = 0
if y > 0:
if Map[y-1][x] == 0 and not visited[y-1][x]:
queue.append((x, y-1))
visited[y-1][x] = 1
elif chance and not visited[y-1][x]:
queue.append((x, y-1))
chance = 0
if y < N-1:
if Map[y+1][x] == 0 and not visited[y+1][x]:
queue.append((x, y+1))
visited[y+1][x] = 1
elif chance and not visited[y+1][x]:
queue.append((x, y+1))
chance = 0
if success:
print(count)
else:
print("-1")- 문제를 어떻게 풀어야할지 감이 아예 오지 않는 문제는 아니었다. 하지만 벽을 부술 수 있다는 조건 하나가 문제 풀이를 굉장히 길어지게 만들었다.
- 처음 내가 택한 방식은, chance라는 변수를 통해 벽 부수기 찬스를 썼는지 안썼는지를 판별하는 방식이었다. chance를 써서 벽을 부쉈을 때는 2차원 배열로 구성된 Map에서 원래라면 갈 수 없는 곳을 방문한 것이 되므로, 따로 visited에 체크하지 않았다.
- 그러나 이 방식을 택하게 되면, 밑의 반례를 해결할 수가 없었다. 반례 해결에 걸림돌이 되는 가장 근본적인 이유는, 벽을 뚫은 뒤에 방문한 지점을 벽을 뚫지 않는 경우에 방문할 수 없기 때문이었다. 따라서 visited를 이중화 하여서, 벽을 뚫은 경우와 뚫지 않은 경우를 구분해야 한다는 것을 깨달았다.
- 처음에는 벽을 뚫는 각 케이스별로 visited 배열을 계속 만들어야 하는지 고민했다. 하지만 일단 벽을 뚫고 나면, 그 뒤의 경우들은 겹치지 않게 판단하는 것이 효율적이므로 굳이 그럴 필요는 없었다.
✔ 정답 코드 [시간 초과 -> 해결]
import sys
from collections import deque
#import copy
N, M = map(int, sys.stdin.readline().split())
Map = []
for _ in range(N):
Map.append(list(map(int, sys.stdin.readline().strip())))
queue = deque()
queue.append((0, 0, 0)) # crack도 0이 안부신거, 1이 부신거
count = 0
success = 0
visited = [[[0]*M for _ in range(N)] for _ in range(2)]
visited[0][0][0] = 1 # 0이 벽 안 부신거, 1이 부신거 (맨 앞에 값)
while queue:
if success:
break
count += 1
for _ in range(len(queue)):
x, y, crack = queue.popleft()
if x == M-1 and y == N-1:
success = 1
break
if x > 0:
if Map[y][x-1] == 0 and not visited[crack][y][x-1]:
queue.append((x-1, y, crack))
visited[crack][y][x-1] = 1
elif Map[y][x-1] == 1 and not crack:
#visited[1] = copy.deepcopy(visited[0])
queue.append((x-1, y, 1))
visited[1][y][x-1] = 1
if x < M-1:
if Map[y][x+1] == 0 and not visited[crack][y][x+1]:
queue.append((x+1, y, crack))
visited[crack][y][x+1] = 1
elif Map[y][x+1] == 1 and not crack:
#visited[1] = copy.deepcopy(visited[0])
queue.append((x+1, y, 1))
visited[1][y][x+1] = 1
if y > 0:
if Map[y-1][x] == 0 and not visited[crack][y-1][x]:
queue.append((x, y-1, crack))
visited[crack][y-1][x] = 1
elif Map[y-1][x] == 1 and not crack:
#visited[1] = copy.deepcopy(visited[0])
queue.append((x, y-1, 1))
visited[1][y-1][x] = 1
if y < N-1:
if Map[y+1][x] == 0 and not visited[crack][y+1][x]:
queue.append((x, y+1, crack))
visited[crack][y+1][x] = 1
elif Map[y+1][x] == 1 and not crack:
#visited[1] = copy.deepcopy(visited[0])
queue.append((x, y+1, 1))
visited[1][y+1][x] = 1
if success:
print(count)
else:
print("-1")- 내가 선택한 방식은 chance 변수를 사용하는 대신, visited 배열을 이중화 하고, queue에 벽을 부쉈는지 부수지 않았는지에 대한 정보도 함께 넣어주는 것이었다.
- 이 코드를 짜기 위해서 밑의 4가지 케이스를 모두 고려해야 했다.
- 벽을 부수지 않은 경우 -> 벽을 부수지 않은 경우 (crack 0 -> 0)
계속해서 벽을 부수지 않으면서 진행하는 케이스이다. 이 경우 밑의 if문에 걸리게 되는데, crack 값에 원래 0이 담겨있었고, 앞으로도 0을 쓸 것이므로 그대로 crack 값을 활용해주면 된다.
if Map[y][x-1] == 0 and not visited[crack][y][x-1]:
queue.append((x-1, y, crack))
visited[crack][y][x-1] = 1- 벽을 부수지 않는 경우 -> 벽을 부술 경우 (crack 0 -> 1)
벽을 부수는 경우로 경우의 수를 뻗어나가는 케이스이다. 처음에는, 벽을 부수지 않는 경우에 체크했던 visited 배열을 넘겨줘야 한다고 생각해서 deepcopy를 활용한 주소 복사가 아닌 값 복사를 해주었다. (그냥 대입연산자로만 처리하면 원래 값까지 바뀌게 되므로) 하지만 이렇게 하면 시간 초과가 발생하게 되며, 벽을 넘어간 뒤에는 다시 돌아오지 못하므로 굳이 넘겨줄 필요가 없었다.
이전과 달리 벽이 존재할 경우에만 걸리도록 보강하였으며, chance 대신 crack을 사용하여 찬스 사용 여부를 판단하였다. visited 배열에 대한 판단은 넣을 필요가 없는데, 그 이유는 어짜피 기존에 crack이 0이었다면 벽이 있는 곳의 visited가 체크되었을리가 없기 때문이다.
이 경우 무조건 visited[1]의 해당 지점을 체크해주고, 이전에 chance 변수를 사용했던 것과 다르게 queue에 crack 값을 1로 넘겨준다.
elif Map[y][x-1] == 1 and not crack: # and not visited[crack][y][x-1]
# visited[1] = copy.deepcopy(visited[0])
queue.append((x-1, y, 1))
visited[1][y][x-1] = 1- 벽을 부술 경우 -> 벽을 부수지 않는 경우 (crack 1 -> 0)
이 케이스는 존재해서는 안된다. 한번 벽을 부순 뒤에는 부순 경우에 대해서만 고려해야 하므로, 이 케이스는 코드 상에서 고려될 필요가 없다.
- 벽을 부술 경우 -> 벽을 부술 경우 (crack 1 -> 1)
벽을 부순 뒤에, 더이상 부술 수 없는 상태로 계속해서 진행하는 케이스이다. 이 경우도 1번 케이스와 동일한 if 문에 걸리게 되는데, Map에서 0인 부분으로만 진행하되, 1이 담겨 있는 crack 값을 바꾸지 않고 계속해서 사용하게 된다.
if Map[y][x-1] == 0 and not visited[crack][y][x-1]:
queue.append((x-1, y, crack))
visited[crack][y][x-1] = 1
- Python3와 PyPy3로 모두 채점이 잘 되는 모습이다. 각 오류 발생 원인은 위에서 모두 설명했기 때문에 생략하도록 하겠다.
- 코드를 길게 작성하여서 모든 케이스를 코드 상에 표시하려고 하기 보다는, 여러 케이스를 코드에 한번에 나타낼 수 있는 방법을 고민해야 할 필요성을 느꼈다. 물론 논리적 사고를 통해 내가 짠 코드가 예외를 허용하지 않고, 모든 케이스를 커버할 수 있는지 검토하는 과정이 필요하다.
- 또한, visited 배열을 매 갈림길마다 계속 만들 필요가 없다던가, visited[1]에 지금까지 표시해온 visited[0]을 넘겨줄 필요가 없다는 것과 같은 것들은 그냥 고민을 통해서 알아내야 한다. 문제를 많이 풀면 이런 감각이 저절로 늘게 될 것이라고 생각한다.
"처음 내가 택한 방식은, chance라는 변수를 통해 벽 부수기 찬스를 썼는지 안썼는지를 판별하는 방식이었다. chance를 써서 벽을 부쉈을 때는 2차원 배열로 구성된 Map에서 원래라면 갈 수 없는 곳을 방문한 것이 되므로, 따로 visited에 체크하지 않았다.
그러나 이 방식을 택하게 되면, 밑의 반례를 해결할 수가 없었다. 반례 해결에 걸림돌이 되는 가장 근본적인 이유는, 벽을 뚫은 뒤에 방문한 지점을 벽을 뚫지 않는 경우에 방문할 수 없기 때문이었다. 따라서 visited를 이중화 하여서, 벽을 뚫은 경우와 뚫지 않은 경우를 구분해야 한다는 것을 깨달았다."
저랑 똑같은 고민을 거치셨네요. 글 잘 읽고 갑니다.