백준-14248-점프 점프

오답

from collections import deque

n = int(input())

graph = [[] for _ in range(n+1)] # 0번 제외
visited = [0] * (n+1)

Ai = list(map(int,input().split()))

for i in range(1,n+1):
    graph[i].append(Ai[i-1])

print(graph)

s = int(input())

def bfs(graph, start, visited):
    queue = deque([start]) #시작노드 큐에 넣음
    visited[start] = 1 # 방문처리

    count = 1

    while queue:
        v = queue.popleft()

        for i in(graph[v]):
            if (v - i) > 0 and (v + i) <= n:    
                if visited[v-i] == 0:
                    queue.append(v-i)
                    visited[v-i] = 1
                    count += 1
                
                if visited[v+i] == 0:
                    queue.append(v+i)
                    visited[v+i] = 1
                    count += 1

    # print(visited)
    return count

print(bfs(graph,s,visited))

• 오답 원인
  • if (v - i) > 0 and (v + i) <= n:
  • 위 부분에서 and 조건으로 동시에 1~n범위 체크를 하게되어 방문한 돌의 개수를 세는데 문제가 생김

정답 코드 [BFS]

from collections import deque

n = int(input())

graph = [[] for _ in range(n+1)] # 0번 제외
visited = [0] * (n+1)

Ai = list(map(int,input().split()))

for i in range(1,n+1):
    graph[i].append(Ai[i-1])

print(graph)

s = int(input())

def bfs(graph, start, visited):
    queue = deque([start]) #시작노드 큐에 넣음
    visited[start] = 1 # 방문처리

    count = 1

    while queue:
        v = queue.popleft()

        for i in(graph[v]):
            if 0 < (v - i) <= n:    
                if visited[v-i] == 0:
                    queue.append(v-i)
                    visited[v-i] = 1
                    count += 1

            if 0 < (v + i) <= n:
                if visited[v+i] == 0:
                    queue.append(v+i)
                    visited[v+i] = 1
                    count += 1

    # print(visited)
    return count

print(bfs(graph,s,visited))

• 조건을 나누어서 방문 가능 확인을 하면 정확하게 개수를 셀 수 있다.

정답 코드 [DFS]

## DFS
n = int(input())
Ai = list(map(int,input().split()))

graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)

for i in range(1,n+1):
    graph[i].append(Ai[i-1])

s = int(input())

count = 1

def dfs(graph, start, visited):
    global count
    visited[start] = 1

    for i in graph[start]:
        if 0 < start - i <= n:
            if visited[start - i] == 0: # 방문 x
                count += 1
                dfs(graph, start - i , visited)
        
        if 0 < start + i <= n:
            if visited[start + i] == 0:
                count += 1
                dfs(graph, start + i, visited)

    return count

print(dfs(graph, s, visited))

 

문제링크