[백준] 11403번: 경로 찾기 (floyd warshall tbc)

https://www.acmicpc.net/problem/11403

initial

it is a textbook dfs/bfs question and yet i wasnt able to solve it

I thought of using a defaultdict(list) and doing dfs on it but actually we can achieve the same traversal way if we adjust the condition like

if graph[from][to]==1

in the logic of

    for i in range(n):
        if graph[node][i]==1 and visited[i]==False:
            visited[i]=True
            dfs(i)

This effectively is checking if there is a valid path from from_node to to_node and if there is, the value would be 1 in that graph.

but in defaultdict, since you know which nodes our from node are connected to, we can directly do like

for i in hola[node]:

in the logic of

    for i in hola[node]:
        if visited[i]==False:
            visited[i]=True
            dfs(i)

but the downside is needing to make another defaultdict(list) from our given graph, which increases execution time. So just follow the former

I also wasnt sure how to give answer from each node to other nodes because when I iterated i from 0 to n and conducted dfs on each i, it all gave the same dfs traversal. But we use a inner for loop and if visited[node] is True, we print 1, else 0.

where to put visited[node]=True?

[wrong] So unlike BFS, we put this condition once dfs on that is about to be executed. Let's say we wrongly put visited[2]=True and do bfs on node 2 (like bfs way). Then maybe dfs will go from 2->7, 7->3 and traversal ends because 3 has no connecting paths to any nodes. But after our dfs, our node 2 has already been marked visited so even though there is no valid path from 2->2 (to itself), we falsely prematurely marked node as visited.So don't.

[fixed] dude it is not a template to be memorised. even for bfs, that above logic is the same so we dont prematurely mark node as visited just like bfs. really try to understand.

dfs

n= int(input())
graph = [list(map(int,input().split())) for _ in range(n)]
hola = defaultdict(list)
for i in range(len(graph)):
    for j in range(len(graph[0])):
        if graph[i][j]==1:
            hola[i].append(j)

def dfs(node):
    visited[node]=True
    for i in hola[node]:
        if visited[i]==False:
            # visited[i]=True
            dfs(i)

for i in range(n):
    visited= [False for _ in range(n)]
    dfs(i)
    for j in range(n):
        if visited[j]:
            print(1, end=' ')
        else:
            print(0,end=' ')
    print()

bfs

same logic here and dont prematurely mark node as visited like explained above.

we use an inner loop in our queue

from collections import deque

n= int(input())
graph = [list(map(int,input().split())) for _ in range(n)]

def bfs(i):
    queue =deque()
    queue.append(i)
    # visited[i]=True
    while queue:
        node = queue.popleft()
        for j in range(n):
            if graph[node][j]==1 and not visited[j]:
                queue.append(j)
                visited[j]=True
    for a in range(n):
        if visited[a]==True:
            print(1, end = ' ')
        else:
            print(0, end = ' ')
    print()


for i in range(n):
    visited=[False for _ in range(n)]
    bfs(i)

a 2d visited list can be used like
https://whitehairhan.tistory.com/333

floyd warshall tbc

https://whitehairhan.tistory.com/333