[BOJ][Python]11403번 풀이

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

11403번: 경로 찾기

import sys
ssr = sys.stdin.readline
sys.setrecursionlimit(10000)

def sol(r,c,start):
    if visited[r][c] == 1:
        g[start][c] = 1
        g[r][c] = 1 
        return
    visited[r][c] = 1
    visited[c][r] = 1
    g[start][c] = 1
    g[r][c] = 1
    for i in range(n):
        if g[c][i] == 1:
            sol(c,i,start)

n = int(ssr())
g = [list(map(int, ssr().split())) for _ in range(n)]
for i in range(n):
    visited = [[0 for _ in range(n)] for _ in range(n)]
    for j in range(n):
        if g[i][j] == 1:
            sol(i,j,i)
for i in g:            
    print(*i)

이번 문제는 조금 찝찝한 문제였습니다. bfs와 dfs 둘 다 사용해봤는데 bfs는 틀리고 dfs는 통과했거든요. 그 외에도 애매하다고 해야할지 문제를 다 풀고 나면 딱 맞아떨어지는 느낌이 드는데 이건 억지로 통과한 것 같다고 할까요. 아무래도 다른 분들 풀이를 좀 찾아봐야 할 것 같습니다.

 

문제 접근은 일단 dfs입니다. 해당 문제는 그래프 탐색을 진행하면서 어떤 노드가 다른 노드까지 갈 수 있을지에 대한 내용을 묻고 있는데요. 예제 1번으로 설명을 드리자면,

3
0 1 0
0 0 1
1 0 0

첫번째 줄은 1번 노드와 2번 노드 사이에 간선이 있고, 2번과 3번, 3번과 1번 사이에 간선이 있음을 나타냅니다. 다만 해당 문제는 방향 그래프를 제시했기 때문에 거꾸로는 갈 수 없습니다(그래서 1,0의 원소가 0입니다). 이 경우에 1번 노드에서 1번으로 가는 방법은 무엇일까요? 1번에서 2번으로 갔다가 3번으로 가서 다시 1로 오는 방법이 있겠죠. 이 경우에 1번은 1번으로 갈 수 있겠습니다만 이게 끝이 아니죠. 그 중간에 있었던 친구들도 하나씩 성립이 된다는 것입니다. 2번에서 3번 3번에서 1번들이 다 성립을 한다는 얘기는 1번에서 2번, 1번에서 3번, 1번에서 1번도 모두 성립한다는 뜻입니다. 이 부분을 놓치면 시간이 많이 걸리는 코드를 작성하게 될 것 같네요. 따라서 저는 start라는 변수를 정의해서 (r,c)를 체크할 때 (start,c)도 가능하다고 체크를 해줬습니다.