수테크📱⌚️👀

문제😂

내 풀🦷

# 4875. 미로
# 출발지에서 목적지에 도착하는 경로가 존재하는지 확인

# 사방 탐색
dx = [0, 1, 0, -1] # 범위 제대로 확인
dy = [-1, 0, 1, 0]
def miro(i, j):
    global result # 결과값 전역변수로 설정해주기
    visited[i][j] = True # 방문한 곳 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}')

내가 잘 못 풀었던 점...

1. 사방 탐색 범위 확인!!! : 잘못 적었드래요.. 꼭 확인하고 적기;;;

2. Runtime error : strip()을 사용해 주어야 한다고 그러는데...

    우리 눈에는 안 보이지만 \n 이 포함 되어 있을지도 모른다고하네요....

    그리고 input()은 알아서 공백을 제거해주지만

    sys를 사용할 떄는 그런 기능이 없어서sys.stdin.readline().strip() 같이 무조건 써줘야 한데요!! 😵‍💫

참고함면 좋을 개념들 ✍️

1) 탐색

: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

 ex) DFS, BFS

2) DFS(깊이 우선 탐색)

• 스택 자료구조에 기초한다..
• 실재로는 스택보다는 재귀 함수를 이용하여 간결하게(?) 구현할 수 있다
• 시간 복잡도 : O(N)

# dfs & 재귀 함수
def dfs(v): # v : 시작점
    global visited, graphs  # 함수 안에서 만들어준게 아니라 안정성을 위해 전역변수로 설정해주었다
    visited[v] = True
    
    for i in graphs[v]: # 인접해 있는 곳 중에 
        if not visited[i]: # 방문을 안했다면
            dfs(i)  # 그 곳을 탐색!!
        
        else:
            continue # 이미 방문한 곳 패스 # 이 부분 안 적어줘도 된다
            
graph = [] # 그래프를 표현하는 인접 리스트(인접 행렬 어려움 ㅜㅜ)
visited = [] # 각 노드가 방문된 정보를 표현하는 1 차원 리스트(true, flase/ 0,1로 구문)

dfs(0)

 => 경로가 있는지 확인할 떄는 dfs 를 사용하는 것이 더 좋다고 하네요..

문제🤔

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)  # 모든 요소가 다 돌아가서 모든 요소가 트루로 바뀌면 끝난다.