수테크📱⌚️👀

문제🤔

NxN 크기의 미로에서 출발지에서 목적지에 도착하는 경로가 존재하는지 확인하는 프로그램을 작성하시오. 도착할 수 있으면 1, 아니면 0을 출력한다.

주어진 미로 밖으로는 나갈 수 없다.

다음은 5x5 미로의 예이다.
 

13101

10101

10101

10101

10021

마지막 줄의 2에서 출발해서 0인 통로를 따라 이동하면 맨 윗줄의 3에 도착할 수 있는지 확인하면 된다.

[입력]
 

첫 줄에 테스트 케이스 개수 T가 주어진다.  1<=T<=50
 

다음 줄부터 테스트 케이스의 별로 미로의 크기 N과 N개의 줄에 걸쳐 미로의 통로와 벽에 대한 정보가 주어진다. 0은 통로, 1은 벽, 2는 출발, 3은 도착이다. 5<=N<=100

[출력]
 

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 계산결과를 정수로 출력하거나 또는 ‘error’를 출력한다.

내 풀🦷

# 4875. 미로
# 출발지에서 목적지에 도착하는 경로가 존재하는지 확인
# 마지막 줄의 2에서 출발, 0인 통로를 따라 이동하면 맨 윗줄의 3에 도착하는지
# 사방 탐색
dx = [0, 1, 0, -1] # 범위 제대로 확인
dy = [-1, 0, 1, 0]
def miro(i, j):
    global result # 결과값 전역변수로 설정해주기
    visited[i][j] = True
    for k in range(4):
        di = i + dx[k]
        dj = j + dy[k] # 하나하나 신경써서 적기
        if 0 <= di < N and 0 <= dj < N and not visited[di][dj]:
            # 탐색안했고 0이면 재귀
            if arr[di][dj] == 0:
                miro(di, dj)
            # 3 도착하면 성공
            elif arr[di][dj] == 3:
                result = 1 # 결과값 성공으로 바꾸기
                break

T = int(input())
for tc in range(1, T + 1):
    N = int(input()) # 미로의 크기
    arr = [list(map(int, input().strip())) for _ in range(N)]
    # 방문 검사
    visited = [[False for _ in range(N)] for _ in range(N)]
    result = 0 # 결과값

    for i in range(N-1, -1, -1):
        for j in range(N-1, -1, -1):
            if arr[i][j] == 2:
                miro(i, j) # 함수에 시작점 넣어주기

    print(f'#{tc} {result}')

벽이 없는곳을 피해서 가야한다고라고라고라파덕 혼자 이러고 있다가..

뭔가 오늘 시험에서 사용한(?) 델타 + dfs에서 배운 개념들 + 재귀 다 쓰면 해결할 듯(?)으로 생각해보았습니다아 🤔

중간에 실수한 부분들 😵‍💫

- 델타 범위 (취중 코딩해서 그런가 잘못 적음;;;;

- dj = i + dk[k] (역시 잘못 적음....)

- 입력 받을 때 strip() 써주지 않아서 런타임에러 발생.... => 사실 아직도 잘 모르겠음 왜인지...

strip()은 공백을 제거하면 되는거자나요??

split()을 안 적어주면 된다 아닌가요??

아시는 멋진분의 댓글 기다리고 있겠습니다...

참고함면 좋을 개념들 ✍️

1) 델타를 이용한 2차 배열 탐색

: 2차 배열의 한 좌표에서 4방향의 인접 배열 요소를 탐색하는 방법(8방도 가능)

arr[0...N-1][0...N-1] # N * N 배열
di = [0, 1, 0, -1] # 하, 우, 상, 좌
dj = [1, 0, -1, 0]
for i in range(N):
	for j in range(N): # 여기까지는 우리가 흔히아는 이차원 배열
    	for k in range(4): # 델차를 이용
        	ni = i + di[k]
            nj = j + dj[k]
            if 0 <= ni < N and 0 <= nj < N: # 범위에 안에 들어있는 인덱스면...
            	f(arr[ni][nj]) # 이 점을 기준으로 더해주든 개수를 세주던 더 나아가던 무궁무진한 문제들이 나올 수 있다

2) 재귀를 활용한 dfs

: 재귀를 활용함으로써 쉽게 dfs를 구현할 수 있다(내용은 안쉬움... 이해하기 힘들었음..)

def dfs(v):
    global visited
    # print(v, "-", end='')
    visited[v] = True # 이거에 해당하면 진행
    # v 노드에서 갈 수 있는 노드를 확인 (인접한 노드)
    for u in graphs[v]:
        if visited[u] == True:  # 방문을 했다면
            continue
        # 방문을 하지 않았다면 방문을 진행
        else: # u가 visited안에 들어있지 않다면 u를 다시 dfs 해주면 된다
            dfs(u)  # 모든 요소가 다 돌아가서 모든 요소가 트루로 바뀌면 끝난다.