요 근래 나를 이렇게 오랫동안 힘들게 한 문제가 있던가..(는 미네랄.. 있긴 하구나) 근데 그것보다 훨씬 힘든 문제였다. 그럼에도 불구하고, 우주의 힘을 끌어모아 스스로 고민하고 코딩해 pass를 받아냈다. 뿌듯 :) 그치만 실전에서 이런 문제를 만났다? 그럼 진짜 빡셌을 듯 싶다..
# 3시간 40분 소요
어려웠던 이유는,
1) 통나무가 세로 방향일 때 5가지, 가로 방향일 때 5가지 조건이 모두 다르기 때문에 하드코딩 필요함.
2) 방문 체크를 관리하기가 까다로움
3) 자료구조 상태 관리
4) (내 기준) 미친 코드 길이..(원래 200줄이 훌쩍 넘었는데 줄였는데도 160줄..)
- 사용 알고리즘 : BFS 최단 시간 알고리즘
- Input 받으며 처음 통나무가 있는 위치 좌표들을 start에, 타겟 위치 좌표를 goal에 저장, 모두 "0"으로 바꿈
- checkDir() 함수에서 첫 통나무 방향이 세로 방향이면 0, 가로 방향이면 1로 리턴
- bfs() 시작하기 전, 전역 변수로 visited, q를 정의한다.
- visited는 Set 자료구조로, (현재 통나무 좌표들) 의 방문 확인 용도로 사용
- q 큐에는 (시작 좌표, 시작 방향, 이동 횟수)를 담음
- 가장 중요한 bfs() 함수
- 큐에서 값을 하나씩 꺼내며
- (현재 통나무 위치 좌표, 방향, 이동 횟수)에 대해
- 크게 현재 통나무 위치가 세로(0), 가로(1)인지 조건문으로 구분하고,
- 그 안에서 U, D, L, R, T 5가지 경우에 대해 일일이 조건문을 작성
- 이동 가능한 곳이라면(flag), 새 위치를 방문 여부를 확인해, 첫 방문일 때만 visited에 넣고, 재검사를 위해 큐에 담는다.(checkVisited() 함수)
- 특히, 회전(T) 일 때 좀 까다로운데, 범위와 통나무 좌우로 나무 있는지 확인하고, 큐에 담을 때 방향을 꼭 바꿔줘야 한다!(0이면 1, 1이면 0으로!!)
- 큐에서 꺼낸 값이 목적지 좌표와 같다면, 이동 횟수를 리턴 후 종료
- 큐에 있는 모든 값을 확인했는데도 목적지에 도착하지 못하면 0 리턴 후 종료
- 큐에서 값을 하나씩 꺼내며
파이썬 코드는 다음과 같다.
from sys import stdin
input = stdin.readline
from collections import deque
def checkDir(temp):
if temp[0][1] == temp[1][1]:
return 0 # 세로 방향 : 0
return 1 # 가로 방향 : 1
def checkVisited(temp, d, cnt):
if temp not in visited: # 첫 방문
visited.add(temp)
q.append((temp, d, cnt+1))
def bfs():
while q:
newTemp, d, cnt = q.popleft()
if newTemp == goal: # 타겟 위치 도착
return cnt
if d == 0: # 세로 방향일 때
for cmd in range(5):
# U
if cmd == 0:
col = deque(newTemp)
r, c = col[0]
if (0 <= r-1 < N) and plain[r-1][c] == "0":
col.pop()
col.appendleft((r-1, c))
checkVisited(tuple(col), 0, cnt)
# D
elif cmd == 1:
col = deque(newTemp)
r, c = col[-1]
if (0 <= r+1 < N) and plain[r+1][c] == "0":
col.popleft()
col.append((r+1, c))
checkVisited(tuple(col), 0, cnt)
# L
elif cmd == 2:
flag = 1
for r, c in newTemp:
if not (0 <= c-1 < N) or plain[r][c-1] == "1":
flag = 0
break
if flag:
col = tuple([(r, c-1) for r, c in newTemp])
checkVisited(col, 0, cnt)
# R
elif cmd == 3:
flag = 1
for r, c in newTemp:
if not (0 <= c+1 < N) or plain[r][c+1] == "1":
flag = 0
break
if flag:
col = tuple([(r, c+1) for r, c in newTemp])
checkVisited(col, 0, cnt)
# T
else:
flag = 1
for r, c in newTemp:
if not (1 <= c < N-1):
flag = 0
break
if plain[r][c-1] == "1" or plain[r][c+1] == "1":
flag = 0
break
if flag: # 가능한 경우
cr, cc = newTemp[1] # 중심 좌표
row = ((cr, cc-1), (cr, cc), (cr, cc+1))
checkVisited(row, 1, cnt) # 방향 바꾸며 큐에 담기
else: # 가로 방향일 때
for cmd in range(5):
# U
if cmd == 0:
flag = 1
for r, c in newTemp:
if not (0 <= r-1 < N) or plain[r-1][c] == "1":
flag = 0
break
if flag:
row = tuple([(r-1, c) for r, c in newTemp])
checkVisited(row, 1, cnt)
# D
elif cmd == 1:
flag = 1
for r, c in newTemp:
if not (0 <= r+1 < N) or plain[r+1][c] == "1":
flag = 0
break
if flag:
row = tuple([(r+1, c) for r, c in newTemp])
checkVisited(row, 1, cnt)
# L
elif cmd == 2:
row = deque(newTemp)
r, c = row[0]
if (0 <= c-1 < N) and plain[r][c-1] == "0":
row.pop()
row.appendleft((r, c-1))
checkVisited(tuple(row), 1, cnt)
# R
elif cmd == 3:
row = deque(newTemp)
r, c = row[-1]
if (0 <= c+1 < N) and plain[r][c+1] == "0":
row.popleft()
row.append((r, c+1))
checkVisited(tuple(row), 1, cnt)
# T
else:
flag = 1
for r, c in newTemp:
if not (1 <= r < N-1):
flag = 0
break
if plain[r+1][c] == "1" or plain[r-1][c] == "1":
flag = 0
break
if flag:
cr, cc = newTemp[1]
col = ((cr-1, cc), (cr, cc), (cr+1, cc))
checkVisited(col, 0, cnt)
return 0
# main
N = int(input())
start, goal = [], []
plain = []
for r in range(N):
plain.append(list(input().rstrip()))
for c in range(N):
if plain[r][c] == "B":
start.append((r, c))
plain[r][c] = "0"
elif plain[r][c] == "E":
goal.append((r, c))
plain[r][c] = "0"
startDir = checkDir(start) # 세로 방향 0, 가로 방향 1
goal = tuple(goal)
visited = set() # 방문 정보 확인(set 자료구조)
visited.add(tuple(start)) # 첫 위치 방문 표시
q = deque([(start, startDir, 0)]) # (시작 좌표, 시작 방향, 이동 횟수)
print(bfs())
- 시간 : 312ms / 메모리 : 128580kb(PyPy3 제출)
- 고찰 : 정말 중간에 여러번 그만 둘까 고민했던 Gold2 문제인데, 끝까지 풀어내어 뿌듯했다ㅠㅠ 처음 알고리즘 시작할 때 DFS보다 BFS가 훨씬 쉽고 간단하다고 생각했는데, 전혀 아니었다. 이전 문제와 마찬가지로 탐색에 중점을 두고 상태 관리를 해주며 BFS를 푸는 건 정말 까다롭더라.. 3시간 30분 정도 걸렸는데, 정신줄 놓지 않고 끝까지 집중 또 집중하며 포기하지 않은 점에서 스스로 성장했음을 느꼈다. Keep Going!
'Problem Solving > boj' 카테고리의 다른 글
[BOJ] 1941. 소문난 칠공주(Python) / DFS, Backtracking (0) | 2021.04.13 |
---|---|
[BOJ] 11725. 트리의 부모 찾기(Python) / BFS, DFS (0) | 2021.04.12 |
[BOJ] 1525. 퍼즐(Python) / BFS (1) | 2021.04.11 |
[BOJ] 14425. 문자열 집합(Python) / Trie 자료구조 (0) | 2021.04.10 |
[BOJ] 11967. 불 켜기(Python) / BFS (0) | 2021.04.09 |