[코테] DFS/BFS 문제 #1

게임 맵 최단거리 (프로그래머스)

1. maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열입니다.
2. maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
3. 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

상대방 진영에 도착하기 위해 지나야하는 칸의 최소값을 반환합니다.
단, 상대방 진영에 도착하지 못했다면, -1을 반환합니다.

풀이

벽이 있는 자리는 0, 지나갈 수 있는 길은 1로 maps가 이루어져 있습니다.
BFS를 이용하여 현재 칸에서 이동할 수 있는 모든 칸에,
현재까지 지나온 칸 +1 을 하여, 지나온 칸의 최소 값을 구합니다.

BFS로 이미 방문한 칸은 방문하지 않도록 구현하여,
더 많은 칸을 지나오는 경로가 있더라도, 기록되지 않습니다.

모든 칸에 최소 값을 구해, 상대방 진영에 도착하기 위해 지나야 하는 칸의 최소값을 구합니다.

코드

python

def solution(maps):
  sizeY = len(maps)
  sizeX = len(maps[0])

  # 인접한 칸 : 4향(상하좌우)
  dy = [1,-1,0,0]
  dx = [0,0,1,-1]

  from collections import deque

  queue = deque([(0,0)])

  while queue:
    y,x = queue.popleft()
    count = maps[y][x]
	
    # 인접한 칸 구하기
    for i in range(4):
      ny = y + dy[i]
      nx = x + dx[i]
	  
      # 적합하지 않은 칸
      if ny<0 or ny>=sizeY or nx<0 or nx>=sizeX: continue
		
      # 벽이 아닌 곳, 이미 방문한 곳이 아닌 곳
      if maps[ny][nx] == 1:
        queue.append((ny,nx))
        # 최소 값 기록
        maps[ny][nx] = count+1

  result = maps[sizeY-1][sizeX-1]
  return result if result != 1 else -1

방문한 칸은 최소 값을 할당했기 때문에, maps[y][x]가 1이 아닌 칸은 이미 방문한 칸으로 하였습니다.
다만, 시작 칸인, maps[0][0]은 1이기 때문에, 값이 2인 칸의 이동에서 3이 할당 될 수 있습니다.
하지만, 구하는 값인 상대방 진영의 값에는 영향을 주지 않기 때문에, 상관없습니다.

가장 먼 노드 (프로그래머스)

n개의 노드가 있는 그래프가 있습니다.
각 노드는 1에서 n까지 번호가 있고, 1번 노드에서 가장 멀리 떨어진 노드를 구하려고 합니다.
가장 멀리 떨어진 노드란, 최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드를 의미합니다.
가장 멀리 떨어진 노드의 개수를 반환합니다.

1. 간선을 나타내는 edge의 [x,y]는 x와 y사이에 간선이 있다는 의미입니다.

풀이

위의 최단거리 문제와 유사합니다.
1에서 부터 각 노드의 최단거리를 구하고, 가장 멀리 떨어져 있는 노드의 개수를 구하면 됩니다.

코드

python

def solution(n,edge):
  graph = [[] for _ in range(n+1)]
  count = [0]*(n+1)

  # 인접 노드를 편하게 구하기 위해, 그래프를 인접리스트로 구현
  for i in edge:
    graph[i[0]].append(i[1])
    graph[i[1]].append(i[0])

  from collections import deque

  queue = deque([1])

  while queue:
    v = queue.popleft()
    c = count[v]

    # 인접하는 노드
    for i in graph[v]:
      # 방문하지 않은 노드
      if count[i] == 0:
        queue.append(i)
        count[i] = c+1

  maxCount = max(count)
  
  # 경로가 가장 먼 노드의 개수, 1번 노드는 제외
  return len([i for i in range(len(count)) if count[i] == maxCount and i != 1])

위의 문제와 마찬가지로, 방문하지 않은 노드에 대한 조건을, 경로가 0인 값으로 했기 때문에,
첫 노드의 경로의 수를 나타내는 count[1]의 값이 변경될 수 있어서 길이를 세는 마지막 코드에 조건을 추가하였습니다.

방문했는지에 대한 visited 변수를 추가하여, 위와 같은 일을 막아도 됩니다.