문제 정보
https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do
접근방법
방문 할 수 있는 위치를 어떻게 찾아갈 수 있을까?
시작점과 끝점을 어떻게 지정할 수 있을까?
방문한 위치는 어떻게 저장할 수 있을까?
끝까지 갔을 때 종료지점이 아니라면 어떻게 되돌아 올 수 있을까?
1차 풀이
miro[r][c] == 2 인 지점의 좌표를 스택에 푸시
배열의 범위를 초과하면 안되니까 범위를 제한해줌
상하좌우 방향을 탐색for 문 을 이용해서 d 값을 변경시켜줌
해서 0인 지점을 일단 스택에 푸시하면서 나아감
만약에 1을 만나거나 배열을 벗어나면 pop 해서 시작지점으로 돌아옴
만약에 3을 만나면 1을 출력하고
3을 못만나면 0을 출력
이런 풀이가 가장 먼저 떠올랐다.
스택과 델타를 이용해서 문제를 해결하려고 했다.
스택에 시작점의 좌표를 입력해 주고 이를 기준으로 델타를 조작해서
다음 위치의 좌표값을 스택에 넣는 방식으로 진행하려고 생각했다.
1. 기준점에서 이동할 수 있는 위치에 대한 좌표를 전부 스택에 넣어준다.
2. 스택의 가장 마지막 값을 기준으로 델타를 이용해서 방향을 탐색한다.
3. 0 을 만나면 다음 0에 해당하는 좌표를 스택에 넣어주고 이를 반복한다.
4. 3을 만났다면 1을 출력하고 만나지 못했다면 스택의 1번 인덱스까지 pop 해주고 2를 반복한다.
for sr in range(n):
for sc in range(n):
if miro[sr][sc] == 2: # 시작점을 검사한다.
stack.append((miro[sr][sc], (sr, sc)))
while miro[sr][sc] != 3:
r = stack[-1][1][0]
c = stack[-1][1][1]
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
if 0 <= nr < n and 0 <= nc < n and miro[nr][nc] == 0:
stack.append((miro[nr][nc], (nr, nc)))
하지만 4 번 고려요소에 의해
시작점이 아닌 위치에서 갈림길을 만나게 됐을 경우 갈림길을 탐색하지 않고 통과하는 문제가 생겼다.
2차 풀이
주변 친구에게 아이디어를 얻었다.
기존에 사용하려던 방식은 스택에 모든 이동가능 좌표를 삽입하는 것 이었지만
삽입한 좌표를 바로 pop 하고 이를 기준으로 탐색하는 방법을 채택했다.
이렇게 하면 1차 풀이에서 고민했던 4번 요소를 고려하지 않아도 된다.
for sr in range(n):
for sc in range(n):
if miro[sr][sc] == 2:
stack.append(sr)
stack.append(sc)
visted = [[0] * n for _ in range(n)]
while stack: #miro[sr][sc] != 3:
c = stack.pop()
r = stack.pop()
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
if 0 <= nr < n and 0 <= nc < n:
if miro[nr][nc] == 3:
dap = 1
break
elif miro[nr][nc] == 0:
stack.append(nr)
stack.append(nc)
하지만 2차 코드에서는 방문처리를 해주지 않았다.
기존에 방문했던 위치이지만 값이 0인 좌표에 가면 스택에 정보를 넣는 문제가 발생했다.
3차 풀이 (정답)
2차 풀이에서 고려했던 요소 + 방문체크를 통해 문제를 해결할 수 있었다.
방문한 위치라면 해당하는 위치를 1 혹은 다른 값으로 변경해서
그 위치의 값을 스택에 넣지 않는 방식으로 문제를 해결할 수 있었다.
while 반복의 조건을 해결하는데 어려움이 있긴 했지만 결과적으로 성공적으로 제출할 수 있었다.
반복문 풀이
# 반복문 풀이
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
for test in range(int(input())):
n = int(input())
miro = [list(map(int, input())) for _ in range(n)]
stack = []
dap = 0
for sr in range(n):
for sc in range(n):
if miro[sr][sc] == 2:
stack.append(sr)
stack.append(sc)
visted = [[0] * n for _ in range(n)]
while stack: #miro[sr][sc] != 3:
c = stack.pop()
r = stack.pop()
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
if 0 <= nr < n and 0 <= nc < n:
if miro[nr][nc] == 3:
dap = 1
break
elif miro[nr][nc] == 0 and visted[nr][nc] != 1:
visted[nr][nc] = 1 # 방문처리
stack.append(nr)
stack.append(nc)
if dap == 1:
break
print(f'#{test + 1} {dap}')
반복문 풀이(함수화)
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
def search(n, arr):
for sr in range(n):
for sc in range(n):
if arr[sr][sc] == 2:
stack.append(sr)
stack.append(sc)
visted = [[0] * n for _ in range(n)]
while stack: #miro[sr][sc] != 3:
c = stack.pop()
r = stack.pop()
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
if 0 <= nr < n and 0 <= nc < n:
if miro[nr][nc] == 3:
return 1
elif miro[nr][nc] == 0 and visted[nr][nc] != 1:
visted[nr][nc] = 1 # 방문처리
stack.append(nr)
stack.append(nc)
return 0
for test in range(int(input())):
n = int(input())
miro = [list(map(int, input())) for _ in range(n)]
stack = []
print(f'#{test + 1} {search(n, miro)}')
재귀 풀이(feat 교수님)
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
def dfs(r, c):
visited[r][c] = 1
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
if 0 <= nr < n and 0 <= nc < n and miro[nr][nc] != 1 and visited[nr][nc] == 0:
dfs(nr, nc)
for test in range(int(input())):
n = int(input())
miro = [list(map(int, input())) for _ in range(n)]
visited = [[0] * n for _ in range(n)]
r = c = er = ec = 0
for i in range(n):
for j in range(n):
if miro[i][j] == 2:
r, c = i, j
elif miro[i][j] == 3:
er, ec = i, j
dfs(r, c)
print(f'#{test + 1} {visited[er][ec]}')
느낀점
풀만 한 것 같으면서도 시간을 많이 잡아먹은 문제였다.
주변 친구의 도움이 없었다면 아직도 해결하지 못했을수도 있다는 생각도 든다.
방향을 탐색하거나, 이동하는 상황에 델타를 쓰는것이 익숙해졌고 금방 떠오르게 됐다.
다만 아직까지 행, 열이 많이 헷갈리는 부분이 있다. 상 하 좌 우 순으로 탐색하고 싶었지만
델타 설정을 잘못해서 좌 우 상 하 순으로 탐색하고 있었다.
물론 범위를 제한해 주었기 때문에 큰 문제는 아니었지만, 행 열 에 대해 자세하게 익혀두자
스택을 배우는 시간에 나온 문제라서 당연히 스택을 이용해야 할 것이라고 생각함 +
문제를 봤을때 스택을 이용하면 될 것 같다는 생각이 들었던건 뿌듯하다.
하지만 DFS 문제라는 생각은 떠올리지 못해서 마이너스
그동안 DFS 문제를 트리나 노드 구조로만 접해와서 그렇게 생각했던 것 같다.
IM 시험을 통과하게 되면 앞으로는 고급 알고리즘 기술들에 대한 충분한 공부를 해야겠다.
'컴퓨터 > Algorithm' 카테고리의 다른 글
백준 15649 N과 M (1) (파이썬) (0) | 2022.09.05 |
---|---|
백준 2667 단지번호붙이기(파이썬) (0) | 2022.09.04 |
백준 7576 토마토(파이썬) (0) | 2022.09.02 |
백준 2477 참외밭(파이썬) (0) | 2022.08.25 |
백준 2628 종이자르기(파이썬) (0) | 2022.08.21 |