1175: 배달

문제 링크

1175: 배달

구현 방식

• 거하게 삽질한 문제..

• 이 문제는 visit 리스트를 5차원으로 선언하여 bfs 탐색으로 풀었다

  • visit 리스트는 [direction][x][y][C1][C2] 순서이다.
  • start위치는 direction을 4로 설정해주면 간편하다!

• bfs 탐색 시, len(queue)만큼씩 한번에 처리하는 방식으로 해줬다 (그냥 하나의 방식임/ node에 cnt 저장하는 방식으로 해도됨)

• 좀 삽질했던 부분이, 상하좌우 이동할 때, 다음 노드들의 flag1, flag2 변수를 따로 처리해줘야 하는데, 이걸 공유하도록 코드를 짰었다.. (그래서 예제 3에서 계속 WA 받음)

  • nflag1 = flag1; nflag2 = flag2 이렇게 node 별로 독립적으로 할당해줌으로써 해결했다

코드

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

board = [list(input()[:-1]) for n in range(N)]

start = tuple(); flag = False
for i in range(N):
    for j in range(M):
        if board[i][j] == 'S': start = (i, j)
        elif board[i][j] == 'C':
            if not flag: board[i][j] = 'C1'; flag = True
            else: board[i][j] = 'C2'

queue = deque([]); queue.append((start[0], start[1], 4, 0, 0))
visit = [[[[[False for j in range(2)] for i in range(2)] for m in range(M)] for n in range(N)] for d in range(5)] # [direction][x][y][C1][C2]
visit[4][start[0]][start[1]][0][0] = True

answer = 0
while queue:
    size = len(queue)
    for s in range(size):
        x, y, pre_dir, flag1, flag2 = queue.popleft()

        if flag1 == 1 and flag2 == 1:
            print(answer); exit()

        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]; nflag1 = flag1; nflag2 = flag2 #nflag1, nflag2로 따로 할당해줘야함! node 별로 독립적인거니까..
            if 0 <= nx < N and 0 <= ny < M and board[nx][ny] != '#' and i != pre_dir:
                if board[nx][ny] == 'C1': nflag1 = 1
                elif board[nx][ny] == 'C2': nflag2 = 1

                if not visit[i][nx][ny][nflag1][nflag2]:
                    visit[i][nx][ny][nflag1][nflag2] = True
                    queue.append((nx, ny, i, nflag1, nflag2))
    answer += 1
print(-1)

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

board = [list(input()[:-1]) for n in range(N)]

start = tuple(); flag = False
for i in range(N):
    for j in range(M):
        if board[i][j] == 'S': start = (i, j)
        elif board[i][j] == 'C':
            if not flag: board[i][j] = 'C1'; flag = True
            else: board[i][j] = 'C2'

queue = deque([]); queue.append((start[0], start[1], 4, 0, 0, 0))
visit = [[[[[False for j in range(2)] for i in range(2)] for m in range(M)] for n in range(N)] for d in range(5)] # [direction][x][y][C1][C2]
visit[4][start[0]][start[1]][0][0] = True

while queue:
    x, y, pre_dir, flag1, flag2, cnt = queue.popleft()

    if flag1 == 1 and flag2 == 1:
        print(cnt); exit()

    for i in range(4):
        nx = x + dx[i]; ny = y + dy[i]; nflag1 = flag1; nflag2 = flag2 #nflag1, nflag2로 따로 할당해줘야함! node 별로 독립적인거니까..
        if 0 <= nx < N and 0 <= ny < M and board[nx][ny] != '#' and i != pre_dir:
            if board[nx][ny] == 'C1': nflag1 = 1
            elif board[nx][ny] == 'C2': nflag2 = 1

            if not visit[i][nx][ny][nflag1][nflag2]:
                visit[i][nx][ny][nflag1][nflag2] = True
                queue.append((nx, ny, i, nflag1, nflag2, cnt+1))
print(-1)

• bfs 부분 조금 수정한 코드