2023/6/30

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

graph = []

# 각 정점당 간선이 하나 밖에 없으므로 그냥 일차원 리스트
for i in range(N):
  val = int(input())
  graph.append(val)

# 방문하였는지 배열에 담는다.
visited = [False] * N

cnt = 0
current_idx = 0

# 목적지가 아니라면 계속 반복
while current_idx != K:
  # 방문했던 곳이라면 목적이 방문 못하는 것이므로 빠져나간다
  if visited[current_idx] == True:
    cnt = -1
    break
  visited[current_idx] = True
  current_idx = graph[current_idx]
  cnt += 1

# 출력
print(cnt)

방향 그래프로 만들어서 문제를 해결하였다.

좀 특이한 점은 각 정점마다 방향 간선이 하나 밖에 없어서 이차원 리스트가 아니라 일차원 리스트로 풀어도 된다고 판단 했다.

해당 방향으로 가면서 visited 리스트를 업데이트하면서 순회하였다.

다른 사람 문제 풀이보니 bfs로 푼사람이 많던데 음.. 그렇게 안푸는게 더 간단한 것 같다

다음은 직접적으로 dfs,bfs 쓰는걸 풀어보겠습니다

2023/7/1

def bfs(i,j):
    global vertexes
    global M
    global visited

    if vertexes[i][j] == '-' and j < M-1 and vertexes[i][j+1] == '-':
        visited[i][j+1] = True
        bfs(i,j+1)
    elif vertexes[i][j] == '|' and i < N-1 and vertexes[i+1][j] == '|':
        visited[i+1][j] = True
        bfs(i+1,j)
    else :
        pass

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

cnt = 0
vertexes = []
visited = [[False] * M for _ in range(N)]

for _ in range(N):
    vertexes.append(list(input()))

for i in range(N):
    for j in range(M):
        if visited[i][j] == False:
            visited[i][j] = True
            cnt += 1
            bfs(i,j)
        else:
            pass
print(cnt)

이번에도.. bfs,dfs는 아닌 것 같았다?? 원래 탐색 문제들이 이런가

‘-’ 문자가 나오면 오른쪽으로 가면서 visited 처리를 하고