알고리즘을 사실 한달만에 다 훑고 문제를 맞을정도의 레벨로 올라간다는 것은 말이 되지 않는다. 요즘은 팀원들과 BFS문제를 깊이 탐구하고있다. 매일 한문제씩 백준에 나와있는 실버와 골드 이상 문제들을 풀고있다. 오늘 이 2문제만 풀고 또풀고 또 생각하고 또다른방식 생각하고 주석달고 생각하고 또풀고 질문하고 또풀고를 반복했다. 첫번째문제는 Walls and Gates, 두번째문제는 벽부수고 이동하기이다. 이 두가지문제는 BFS 문제인데, 혼자서 생각도 많이한거라 애착이 많이가서 적게되었다. 특히 첫번째문제는 나의 BFS이해력을 향상시키고, 생각의전환(?)에 도움이 되게 하였다.
by leetcode, https://leetcode.com/problems/walls-and-gates/solution/
나는 보통 기초적인 BFS를 많이 풀었는데 보통 방문했는지, 최단거리로 가는 횟수 이런식으로 문제가 많이 나왔어서 이런문제와같이 어떤 위치에서 가까운 경우를 찾는것에 익숙하지않다. 사실 내가 생각해내야하긴하지만 그래도...아무튼 게이트 위치를 중심으로 큐를 데크를 통해서 사용해서 풀어야한다.
from collections import deque
def wallsAndGates(rooms):
'''
Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
'''
empty_room = 2**31 -1 # 2147483647
m = len(rooms) #행 길이
n = len(rooms[0]) #열 길이
directions = [0, 1, 0, -1, 0] #네비게이션 준비: 위 아래 오른쪽 왼쪽 이렇게 표현하는것이 더 느낌있어보인다.
q = deque() #BFS니까 큐 장착하고, 데크 준비합시다
for i in range(m):
for j in range(n):
if rooms[i][j] == 0:
q.append((i, j)) #예시 인풋일경우: deque([(0, 2), (3, 0)])
while q:
i, j = q.popleft() # q 상태: (0,2) (3,0)
for k in range(4):
x = i + directions[k]
y = j + directions[k+1]
# (x, y) -> (0,2): (0, 3), (1, 2), (0, 1), (-1, 2)
# (x, y) -> (3, 0): (3, 1), (4,0), (3, -1), (2, 0)
if x < 0 or x >=m or y < 0 or y >=n:
continue
if rooms[x][y] != empty_room:
continue
rooms[x][y] = rooms[i][j] + 1 #게이트 근처에 있으면 1, 그리고 근처 1인 좌표를 저장해주고,
q.append((x, y)) #나중에 큐를 이용해서 또 게이트와 얼마나 먼 좌표인지 계산하고 거리만큼 더하기 해준다.
return rooms #좌표에 나와있는 빈칸에 게이트로부터 얼만틈 먼지 다 적어놓은 것을 반환해준다.
rooms = [[2147483647,-1,0,2147483647],
[2147483647,2147483647,2147483647,-1],
[2147483647,-1,2147483647,-1],
[0,-1,2147483647,2147483647]]
print(wallsAndGates(rooms))두번째 문제는, 우리팀이 정해서 풀어본 문제인데, 백준에서 나온 문제이다. 내 실력에서 이 문제는 최상급에 속하고 굉장히 어렵다. 이것은 보통 2차배열을 쓰는 문제와 다르게 3차까지 생각해줘야한다. 사실 이 문제를 접근할때, 2차원으로 생각하여 벽을 부수는 기능을 더하는것에 애를 먹었다. 우선 3차원 배열 방식까지는 아니여도 카운트해주는 주머니를 하나 만들어서, 벽을 만났을때 부셨을경우와 부시지 않고 그냥 갔을때를 비교하여 min()을 써서 최소한의 경로를 출력하려고 했다. 하지만, 실패. 결과적으로, 풀지 못했고....아이디어만 남긴채...풀이를 보고 열심히 연구했다. 팀원들도 풀지못했지만, 에이스 팀원이 알려주어서 잘 풀게되었다. 우선 제일 중요한게 if문 밑에 상황이다.
from collections import deque
import sys
#입력하자 인풋 확인하고, 문제 잘 읽어서 형식대로 절차 진행하자
#백준문제풀때 눈감고 import sys 써주고
input = sys. stdin.readline # 이것도 써주고
rows, cols = map(int, input().split()) #이것도 써주는데, map부터가 중요
matrix = [] #행렬 인풋 받아올준비합시다.
for _ in range(rows):#인풋받은 숫자들을 바탕으로 행렬을 만들어줍시다.
matrix.append(list(map(int, input().strip()))) #정수로 받아오게 해준다.
visited = [[[0] * 2 for _ in range(cols)] for _ in range(rows)] #모든 구역을 0으로 깔아준다 -> 방문 안했다는뜻으로
visited[0][0][0] = 1 #3차원 배열로 벽을 부수는게 가능한지 불가능한지 입력해준다. visited[0][0][0]: 벽안부수고감 visited[0][0][1]:벽부수고감
directions = [0, 1, 0, -1, 0] #네비게이션기능이라고 내가 부른다. 위 아래 왼쪽 오른쪽 조건을 검사해서 이동
def bfs(x, y, z):
q = deque() #bfs최단경로탐색을 위해서는 큐를 사용 해야하고, 그렇기때문에 데크를 사용한다.
q.append((x, y, z)) #받아온 x, y, z로 시작! 여기선 0,0,0 에서 시작
while q:
a, b, c = q.popleft() # 맨처음에 들어간것부터 들어간다 (0, 0, 0) 시작
if a == rows - 1 and b == cols - 1: #인풋값 좌표가 입력한 행렬의 끝좌표이면 / 도달한 경우
return visited[a][b][c] #visited[5][3][c] 바로리턴해버려
for k in range(4): #위 아래 왼쪽 오른쪽 검사실시!
nx = a + directions[k] #위에 제시한 directions대로 x 한칸 옆에가서 검사하고
ny = b + directions[k+1] #y한칸 가서 검사하기
if nx < 0 or nx >= rows or ny < 0 or ny >= cols:
continue # 내가 입력한 행렬위에서 네비게이션이 움직이지 않으면 위로올라가.
if matrix[nx][ny] == 1 and c == 0: # 벽이 있고 + 벽 아직 안부순상태
visited[nx][ny][1] = visited[a][b][0] + 1 #이전상태 (벽 안부순상태) 에다가 부수고 갔다는 것을 말해준다
q.append((nx, ny, 1)) #큐에다가 저장 #벽 부수고 간걸로 저장
elif matrix[nx][ny] == 0 and visited[nx][ny][c] == 0: #네비했는데, 벽없고, 방문한적없으면
visited[nx][ny][c] = visited[a][b][c] + 1 #한칸 이동시키고
q.append((nx, ny, c)) #큐에다가 저장
return -1 #목표지점 도달 못하면 -1 리턴
print(bfs(0, 0, 0))(1) 벽이 있는 상태이고, 벽을 부수지 않은상태 -> 이것은 벽 부수고 간걸로 큐를 저장 (한칸 이동).
(2) 벽이 없는 상태이고, 방문하지 않은상태 -> 큐에다가 한칸 이동하고 저장.
이부분이 제일 어려웠다. 결국 삼차원을 만들어 준것에서 마지막 부분이 벽이 부서진상태인지 아닌지를 봐주는 경우이다. 지금 백준 골드4레벨문제가 이정도인데 앞으로 이런문제를 더 많이 만난다고한다. 보통 이런레벨문제는 대부분 이렇게 된다고한다. 우선 이 두문제. 오늘 하루종일 생각많이해서 풀었다. 뿌듯하다. 복습철저히.
