[백준/Python] 14940. 쉬운 최단거리

2024. 11. 19. 15:26·코딩테스트/BAEKJOON
728x90
반응형

📌문제 유형: 그래프 탐색 (BFS)

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

 

 

 

📌 풀이 

 

전형적인 BFS 문제이다.

 

단, 시작점이 (0,0) 이 아니라 2 값을 갖고 있는 위치부터라는 점! 따라서 먼저 2의 값을 가진 위치를 찾아야 한다. 

 

그 뒤에 모든 지점까지의 최단거리를 출력하라고 한다. 최단거리는 BFS로 구할 수 있다. 

 

이때 움직일 수 있는 방향이 상하좌우이므로, dx/dy를 선언해 bfs() 안에서 for문을 통해 한 지점이 갈 수 있는 상하좌우 4곳을 살펴볼 수 있도록 한다. 이때 갈 수 있는 곳은 queue에 담는다. 

 

여기서 포인트는, 거리 값을 visited에 누적합으로 표현한다는 점이다. 

 

1. 모든 지점에 대해 visited[i][j] = -1로 초기화하고,
2. popleft()한 지점 (x,y) 에 대해 nx/ny (next_x, next_y) 를 찾는다. 
3. 각 nx/ny에 대해 graph 상에서 1이면 갈 수 있으므로, visited[nx][ny] = visited[x][y] + 1로 누적합을 한다. 
4. 각 nx/ny에 대해 graph 상에서 0이면 갈 수 없으므로, visited[nx][ny] = 0으로 둔다. 

 

이를 코드로 표현하면 아래와 같다. 

 

⭐ 그래프 탐색의 기본적인 문제이므로 암기해두자. !

 

from collections import deque
N, M = map(int, input().split())
graph = []
for i in range(N):
    tmp = list(map(int, input().split()))
    # if 2 in tmp:
    #     start = [i, tmp.index(2)]
    graph.append(tmp)

visited = [[-1 for _ in range(M)] for _ in range(N)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def bfs(i, j):
    q = deque()
    q.append((i,j))
    visited[i][j] = 0

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx<N and 0<=ny<M and visited[nx][ny] == -1:
                if graph[nx][ny] == 1:
                    q.append((nx, ny))
                    visited[nx][ny] = visited[x][y] + 1
                elif graph[nx][ny] == 0:
                    visited[nx][ny] = 0

# bfs(start[0], start[1])
for i in range(N):
    for j in range(M):
        if graph[i][j] == 2:
            bfs(i, j)

# for i in range(N):
#     print(visited[i])
for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
            print(0, end=' ')
        else:
            print(visited[i][j], end=' ')
    print()
728x90
반응형
저작자표시 비영리 변경금지 (새창열림)

'코딩테스트 > BAEKJOON' 카테고리의 다른 글

[백준/Python] 1874. 스택 수열  (1) 2024.11.19
[백준/Python] 11403. 경로 찾기  (1) 2024.11.19
[백준/Python] 1463. 1로 만들기  (1) 2024.11.18
[백준/Python] 1003. 피보나치 함수  (2) 2024.11.18
[백준/Python] 17219. 비밀번호 찾기  (2) 2024.11.18
'코딩테스트/BAEKJOON' 카테고리의 다른 글
  • [백준/Python] 1874. 스택 수열
  • [백준/Python] 11403. 경로 찾기
  • [백준/Python] 1463. 1로 만들기
  • [백준/Python] 1003. 피보나치 함수
heeya16
heeya16
개발 공부 냠냠
  • heeya16
    개발자 희야
    heeya16
  • 전체
    오늘
    어제
    • 분류 전체보기 (105)
      • 코딩테스트 (66)
        • 프로그래머스 (38)
        • SWEA (2)
        • BAEKJOON (26)
      • 알고리즘 (7)
      • 자료구조 (19)
      • 프로젝트 (5)
      • 취업 주르륵 (2)
      • 데이터베이스 (0)
      • IT지식 (2)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    1003
    10448
    10773
    10월
    10진수
    11047
    11399
    11403
    11866
    1449
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
heeya16
[백준/Python] 14940. 쉬운 최단거리
상단으로

티스토리툴바