[백준] 3055번, 탈출 (Python)

2021. 8. 12. 13:55·알고리즘/백준
728x90
반응형

문제

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

 

3055번: 탈출

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제

www.acmicpc.net

 

코드

import collections
import sys
input = sys.stdin.readline

n, m = map(int, input().split())

graph = [list(input().strip()) for _ in range(n)]
distance = [[0] *m for _ in range(n)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
queue = collections.deque()

def bfs(Dx,Dy):
    while queue:
        x,y = queue.popleft()
        if graph[Dx][Dy] == 'S':
            return distance[Dx][Dy]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if (graph[nx][ny] == '.' or graph[nx][ny] == 'D') and graph[x][y] == 'S':
                    graph[nx][ny] = 'S'
                    distance[nx][ny] = distance[x][y] + 1
                    queue.append((nx,ny))
                elif (graph[nx][ny] =='.' or graph[nx][ny] =='S') and graph[x][y] == '*':
                    graph[nx][ny] = '*'
                    queue.append((nx,ny))
    return "KAKTUS"


for x in range(n):
    for y in range(m):
        if graph[x][y] == 'S':
            queue.append((x,y))
        elif graph[x][y] == 'D':
            Dx,Dy = x,y

for x in range(n):
    for y in range(m):
        if graph[x][y] == '*':
            queue.append((x,y))

print(bfs(Dx,Dy))

 

queue에 고슴도치 위치를 넣어준후에 물에 위치를 넣어줬다 고슴도치가 먼저 이동하고 물이 차도록 만듬

=> 고슴도치가 이동했더라도 물이 이동할 위치라면 고슴도치를 덮어쓰기 때문

 

queue에 고슴도치, 물 순서로 들어있으므로 계속 고슴도치 이동후 물 이동하여 graph 값을 변환시켜준다.

 

현재위치가 'S'이면 고슴도치가 움직일 차례이다.

고슴도치는 빈칸('.')과 비버의집('D')인 경우만 이동가능하다.

 

현재위치가 '*'이면 물이 움직일 차례이다.

물은 빈칸('.')과 고슴도치('S')인 경우만 이동가능하다.

 

비버의집 위치를 저장후에 bfs를 돌리고 만약 비버의집 위치가 'S' 고슴도치라면 distance값 반환

bfs를 모두 돌았는데 'S'가 아니라면 'KAKTUS' 반환하면 된다.

반응형
저작자표시 (새창열림)

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 1759번, 암호 만들기 (Python)  (0) 2021.08.13
[백준] 3190번, 뱀 (Python)  (0) 2021.08.12
[백준] 10451번, 순열 사이클 (Python)  (0) 2021.08.08
[백준] 1389번, 케빈 베이컨의 6단계 법칙 (Python)  (0) 2021.08.07
[백준] 2193번, 이친수 (Python)  (0) 2021.08.03
'알고리즘/백준' 카테고리의 다른 글
  • [백준] 1759번, 암호 만들기 (Python)
  • [백준] 3190번, 뱀 (Python)
  • [백준] 10451번, 순열 사이클 (Python)
  • [백준] 1389번, 케빈 베이컨의 6단계 법칙 (Python)
wookcode
wookcode
공부한 내용들을 정리하고 기록하는 블로그입니다.
    반응형
  • wookcode
    wookcode
    wookcode
  • 전체
    오늘
    어제
    • 카테고리 (196)
      • study (1)
        • 아파치 카프카 애플리케이션 프로그래밍 with 자.. (0)
        • 인프런 (1)
      • Live Study (15)
      • Programming (14)
        • Java (8)
        • Python (1)
        • Springboot (5)
        • MSA (0)
      • 알고리즘 (117)
        • 백준 (58)
        • 프로그래머스 (59)
      • 에러로그 (5)
      • 항해99 (23)
      • 면접 (1)
      • 프로젝트 (1)
      • CS (19)
        • 네트워크 (2)
        • 운영체제 (2)
        • 데이터베이스 (2)
        • 컴퓨터구조 (1)
        • Java (8)
        • Spring (4)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    괄호
    카카오인턴
    버그
    파이썬
    SFlash
    에러
    인프런
    조합
    김영한
    백준
    브루트포스
    java
    항해마켓
    spring
    해결
    항해99
    미니프로젝트
    SpringBoot
    회고
    프로그래머스
    실전프로젝트
    스파르타코딩클럽
    후기
    jpa
    코딩테스트
    그리디
    카카오코딩테스트
    정리
    orm
    알고리즘
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.4
wookcode
[백준] 3055번, 탈출 (Python)
상단으로

티스토리툴바