[백준] 14497번 : 주난의 난 - 파이썬

아이디어 : BFS, 2차원 리스트, deque

파이썬 2차원 리스트 생성

# 3 x 4 이차원 리스트 생성
matrix = [[0 for j in range(4)] for i in range(3)]

위 코드에서 range() 함수를 사용하여 각 행과 열의 길이를 지정하고, 0으로 초기화된 리스트를 생성함

파이썬 2차원 배열 입력

in_graph = []
for _ in range(N):
    in_graph.append(list(map(str, input().strip())))

list(map(str, input().strip())) 는 입력된 문자열을 입력받아 str 자료형으로 변환한 리스트를 를 반환함

in_graph 는 각 N행의 리스트 원소를 입력 받음

파이썬 deque 자료구조

from collections import deque

que = deque()

아이디어 - distance 이차원 리스트

방문 여부 & 점프 횟수 사용

 

문제 해결 과정

jump 시작 시 모든 인접 0을 방문할 수 있다 !
1을 만난 경우, 쓰러트리고(?) 다음 점프에 방문할 수 있다.

따라서, 처음 jump에 인접 0은 deque의 appendleft 를 하고, 1은 deque의 append 를 해야한다 ! 

 

# -*- coding: utf-8 -*- 
import sys
import queue
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
y1, x1, y2, x2 = map(int, input().split())

in_graph = []
for _ in range(N):
    in_graph.append(list(map(str, input().strip())))

distance = [[-1 for j in range(M)] for i in range(N)]

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

que = deque()

def bfs(y, x):
    que.append((y,x))
    distance[y][x] = 0
    while que:
        qy, qx = que.popleft()
        for i in range(4):
            gy = qy+dy[i]
            gx = qx+dx[i]
            if 0 <= gx < M and 0 <= gy < N:
                if in_graph[gy][gx] == '0' and distance[gy][gx] == -1:
                    # print("no people, so put")
                    que.appendleft((gy,gx))
                    distance[gy][gx] = distance[qy][qx]
                elif in_graph[gy][gx] == '1' and distance[gy][gx] == -1:
                    # print("hit")
                    que.append((gy,gx))
                    distance[gy][gx] = distance[qy][qx] + 1
                elif in_graph[gy][gx] == '#':
                    # print("find")
                    distance[gy][gx] = distance[qy][qx] + 1
                    print(distance[gy][gx])
                    return True
    return False

bfs(y1-1,x1-1)

 

추가 - 고찰

deque 를 사용할 생각을 못해서

처음엔 큐 자료구조 2개 사용하여 구현하였다 ㅜ.ㅜ

또한 distance 이차원 리스트를 방문 여부 & 점프 횟수 로 정의하여 사용할 수 있다고 생각 못했다 ! 

 

기존 로직

- que : 0을 만났을 때 좌표 put

- que_hit : 1을 만났을 때 좌표 put

1-1. jump !

1-2. 0은 que, 1은 que_hit 에 put

1-3. visit 함수 업데이트

2.  que 가 빌 때까지 위 로직 반복

3. que 가 비면 que 에 que_hit 복사 후, 1번 로직 반복

4. #을 만나면 종료

# -*- coding: utf-8 -*- 
import sys
import queue

input = sys.stdin.readline

N, M = map(int, input().split())
y1, x1, y2, x2 = map(int, input().split())

in_graph = []
for _ in range(N):
    in_graph.append(list(map(str, input().strip())))

visit = [[0 for j in range(M)] for i in range(N)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]

que = queue.Queue()
que_hit = queue.Queue()

def bfs(y, x):
    result = 1
    que.put((y,x))
    while not que.empty():
        qy, qx = que.get()
        for i in range(4):
            gy = qy+dy[i]
            gx = qx+dx[i]

            if gx < 0 or gx == M or gy < 0 or gy == N:
                continue

            if in_graph[gy][gx] == '0' and visit[gy][gx] == 0:
                visit[gy][gx] = 1
                que.put((gy,gx))
            elif in_graph[gy][gx] == '1' and visit[gy][gx] == 0:
                visit[gy][gx] = 1
                in_graph[gy][gx] = '0'
                que_hit.put((gy,gx))
            elif in_graph[gy][gx] == '#':
                print(result)
                return True
        if que.empty():
            result += 1
            while not que_hit.empty():
                que.put(que_hit.get())
    return False

bfs(y1-1,x1-1)

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

14497번: 주난의 난(難)