감옥

DFS setting(python)

• 아주 기본적인 dfs문제인데, cnt를 global로 설정하면, 문제가 생기지 않을까??에서 의문이 생겼다…

N, M = map(int, input().split())

# basic setting
VERTICES_NUM = N
EDGES_NUM = M

# +1 for using original index
graph = [[] for _ in range(VERTICES_NUM + 1)]
visited = [False for _ in range(VERTICES_NUM + 1)]

# initializing
start_points = []
end_points = []

for _ in range(M):
    x, y = map(int, input().split())
    start_points.append(x)
    end_points.append(y)

for start, end in zip(start_points, end_points):
    graph[start].append(end)
    graph[end].append(start)

# dfs function
cnt = 0
def dfs(vertex):
    global cnt 
    for curr_v in graph[vertex]:
        if not visited[curr_v]:
            cnt += 1
            visited[curr_v] = True
            dfs(curr_v)
    return

# simulation

root_vertex = 1
visited[root_vertex] = True
dfs(root_vertex)
print(cnt)

• 두 방향탈출

  • 왜 안될까??? …. 진짜 도저히 감이 안잡히는데? ㅋㅋㅋ

# input and draw grid
n, m = map(int, input().split())
grid = []
for _ in range(n):
    grid.append(list(map(int, input().split())))

visited = [[0] * m for _ in range(n)]

# dx, dy technique
dx = [1, 0]
dy = [0, 1]
nx, ny = 0, 0


# can_go condition
def in_range(x, y):
    if 0 <= x < n and 0 <= y < m: return True
    else: return False

def can_go(x, y):
    if in_range(x, y) and grid[x][y] == 1:
        return True
    else : return False

def dfs(x, y):
    global order
    
    nx , ny = x, y
    for i in range(2):
        nx, ny = nx + dx[i], ny + dy[i]
        if can_go(nx, ny) and not visited[nx][ny]:
            visited[nx][ny] = 1
            dfs(nx, ny)
    return


visited[0][0]= 1
dfs(0, 0)

print(visited[n-1][m-1])