길찾기 문제(python,c++)

길찾기문제

방향값을 미리 코드에 짜두고 for문으로 순회하는 기법을 꼭 익혀두자!

방문체크필요 , 각 칸이 노드, 상하좌우 4방향의 간선

 

# python

from collections import deque
dy = (0,1,0,-1)
dx = (1,0,-1,0)
chk = [[False] * 100 for _ in range(100)]
N = int(input())

def is_valid_coord(y,x):
    return 0<=y<N and 0<=x<N

def bfs(start_y,start_x):
    q = deque()
    q.append((start_y,start_x))
    while len(q) > 0:
        y,x = q.popleft()
        chk[y][x] = True # 방문체크
        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            
            # 유효,방문X 노드일경우 q에 넣는다.
            if is_valid_coord(ny,nx) and not chk[ny][nx]:
                q.append((ny,nx))

 

# C++

const int dy[4] = {0, 1, 0, -1};
const int dx[4] = {1, 0, -1, 0};
int N;
bool chk[100][100];

bool isValidCoord(int y,int x){
    return 0<=y && y<N && 0<=x && x<N;
}

void dfs(int y,int x){
    chk[y][x] = true;
    for(int k=0;k<4;++k){
        int ny = y+dy[k];
        int nx = x+dx[k];
        if(isValidCoord(ny,nx) && !chk[ny][nx])
            dfs(ny,nx);
    }
}