[BOJ] #4179 ๋ถˆ! (Python, BFS)

    ๋ฐ˜์‘ํ˜•

    ๐ŸŒฑ ๋ฌธ์ œ

     

    4179๋ฒˆ: ๋ถˆ!

    ์ž…๋ ฅ์˜ ์ฒซ์งธ ์ค„์—๋Š” ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋œ ๋‘ ์ •์ˆ˜ R๊ณผ C๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹จ, 1 ≤ R, C ≤ 1000 ์ด๋‹ค. R์€ ๋ฏธ๋กœ ํ–‰์˜ ๊ฐœ์ˆ˜, C๋Š” ์—ด์˜ ๊ฐœ์ˆ˜์ด๋‹ค. ๋‹ค์Œ ์ž…๋ ฅ์œผ๋กœ R์ค„๋™์•ˆ ๊ฐ๊ฐ์˜ ๋ฏธ๋กœ ํ–‰์ด ์ฃผ์–ด์ง„๋‹ค. ๊ฐ๊ฐ์˜ ๋ฌธ์ž

    www.acmicpc.net

     

    ๐ŸŒฑ ํ’€์ด

    ์ง€ํ›ˆ์ด๊ฐ€ ๋ฏธ๋กœ์—์„œ ํƒˆ์ถœํ•  ์ˆ˜ ์žˆ๋Š” ์ตœ์†Œ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ธ๋ฐ, ๋ถˆ๋„ ๊ฐ™์ด ์‚ฌ๋ฐฉ์œผ๋กœ ํ™•์‚ฐํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์›€์ง์ด๋Š” ๊ฐ์ฒด๊ฐ€ 2๊ฐœ์ธ BFS ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

    1. ๋ฏธ๋กœ ์ •๋ณด์™€ ์ง€ํ›ˆ์ด์™€ ๋ถˆ์˜ ์ดˆ๊ธฐ ์œ„์น˜ ์ •๋ณด

    ์šฐ์„  ๋ฏธ๋กœ ์ •๋ณด๋ฅผ graph์— ์ €์žฅํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  graph์—์„œ ์ง€ํ›ˆ์ด์˜ ์ดˆ๊ธฐ ์œ„์น˜("J")์™€ ๋ถˆ์˜ ์ดˆ๊ธฐ ์œ„์น˜("F")๋ฅผ ๊ฐ๊ฐ jihoon_start์™€ fire_start์— ์ €์žฅํ•ฉ๋‹ˆ๋‹ค.

    h, w = map(int, input().split())
    visited = [[False] * w for _ in range(h)]
    
    graph = []
    for _ in range(h):
        graph.append(list(input())[:w])
    
    fire_start = []
    for i in range(h):
        for j in range(w):
            if graph[i][j] == "J":
                jihoon_start = (i, j)
                graph[i][j] = 0
            elif graph[i][j] == "F":
                fire_start.append((i, j))

     

    2. ๋ถˆ์˜ ํ™•์‚ฐ ์ •๋ณด ์ €์žฅํ•˜๊ธฐ

    ์‹œ๊ฐ„์ด ์ง€๋‚  ๋•Œ์— ๋ถˆ์ด ๋จผ์ € ํ™•์‚ฐ๋˜๊ณ  ํ™•์‚ฐ๋œ ๊ณณ์—๋Š” ์ง€ํ›ˆ์ด๊ฐ€ ์ด๋™ํ•  ์ˆ˜ ์—†๊ธฐ ๋•Œ๋ฌธ์— ๋ถˆ์˜ ํ™•์‚ฐ ์ •๋ณด๋ฅผ ๋ฏธ๋ฆฌ ์ €์žฅํ•ฉ๋‹ˆ๋‹ค.

    def fire_bfs(start):
        global graph, w, h
        fire = deque([])
        visited = [[False] * w for _ in range(h)]
        for s in start:
            y, x = s
            fire.append((y, x))
            visited[y][x] = True
    
        while fire:
            y, x = fire.popleft()
    
            for i in range(4):
                ny, nx = y + dy[i], x + dx[i]
    
                if ny < 0 or nx < 0 or ny > h - 1 or nx > w - 1:
                    continue
                if visited[ny][nx] == False and graph[ny][nx] != "#":
                    graph[ny][nx] = graph[y][x] + "F"
                    visited[ny][nx] = True
                    fire.append((ny, nx))
                    
    fire_bfs(fire_start)
    • ๋ถˆ์€ ๋งค ์‹œ๊ฐ„๋งˆ๋‹ค ์‚ฌ๋ฐฉ(์œ„, ์•„๋ž˜, ์™ผ์ชฝ, ์˜ค๋ฅธ์ชฝ)์œผ๋กœ ํ™•์‚ฐ๋˜๊ธฐ ๋•Œ๋ฌธ์— bfs ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•ด ํ™•์‚ฐ ์ •๋ณด๋ฅผ ์ €์žฅํ•ฉ๋‹ˆ๋‹ค.
    • ๋ถˆ์˜ ํ™•์‚ฐ ์ •๋ณด๋Š” ์‹œ๊ฐ„ ์ •๋ณด์™€ ํ•จ๊ป˜ ์ €์žฅ๋˜์–ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ €๋Š” ์‹œ๊ฐ„์ด ์ง€๋‚  ์ˆ˜๋ก F์˜ ๊ฐœ์ˆ˜๋ฅผ ๋Š˜๋ ค์„œ graph์— ์ €์žฅํ•ด์ฃผ์—ˆ์Šต๋‹ˆ๋‹ค.

    • ์˜ˆ๋ฅผ ๋“ค์–ด ์œ„์™€ ๊ฐ™์€ ์˜ˆ์‹œ์—์„œ fire_bfs์˜ ํ•จ์ˆ˜๊ฐ€ return๋œ ๋’ค, graph์˜ ๊ฒฐ๊ณผ๋Š” ์œ„์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ F์˜ ๊ฐœ์ˆ˜๋กœ ๋ถˆ์ด ํ™•์‚ฐ๋œ ์‹œ๊ฐ„ ์ •๋ณด๋ฅผ ํŒŒ์•…ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

     

    3. ์ง€ํ›ˆ์ด ์ด๋™์‹œํ‚ค๊ธฐ

    ์ด์ œ ์ง€ํ›ˆ์ด๋ฅผ ์ด๋™์‹œํ‚ฌ ์ฐจ๋ก€์ž…๋‹ˆ๋‹ค. ์ง€ํ›ˆ์ด๋„ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ์‚ฌ๋ฐฉ์œผ๋กœ ์ด๋™ ๊ฐ€๋Šฅํ•˜๊ธฐ ๋•Œ๋ฌธ์— bfs ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•ด์„œ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•ฉ๋‹ˆ๋‹ค.

    def jihoon_bfs(start):
        global graph, w, h
        y, x = start
        jihoon = deque([(y, x)])
        graph[y][x] = 0
        visited = [[False] * w for _ in range(h)]
        visited[y][x] = True
    
        while jihoon:
            y, x = jihoon.popleft()
    
            for i in range(4):
                ny, nx = y + dy[i], x + dx[i]
    
                if ny < 0 or nx < 0 or ny > h - 1 or nx > w - 1:
                    return graph[y][x] + 1
                if visited[ny][nx] == False and graph[ny][nx] != "#":
                    if graph[ny][nx] == "." or graph[ny][nx].count("F") - 1 > graph[y][x] + 1:
                        visited[ny][nx] = True
                        jihoon.append((ny, nx))
                        graph[ny][nx] = graph[y][x] + 1
        return -1
    • ์ด ๋•Œ, ์ด๋™๊ฐ€๋Šฅํ•œ ๊ฒฝ์šฐ๋ฅผ graph[ny][nx]๊ฐ€ "."์ผ ๋•Œ์™€ ๋ถˆ์ด ํ™•์‚ฐ๋œ ์‹œ๊ฐ„(graph[ny][nx].count("F") - 1)๋ณด๋‹ค ์ง€ํ›ˆ์ด์˜ ํ˜„์žฌ ์ด๋™ ์‹œ๊ฐ„(graph[y][x] + 1)์ด ์ž‘์„ ๋•Œ๋กœ ํ•ฉ๋‹ˆ๋‹ค.
    • ny, nx๊ฐ€ graph์˜ ๋ฒ”์œ„๋ฅผ ๋ฒ—์–ด๋‚˜๋ฉด ์ง€ํ›ˆ์ด๊ฐ€ ํƒˆ์ถœํ–ˆ๋‹ค๋Š” ์˜๋ฏธ์ด๋ฏ€๋กœ ์ตœ๋‹จ ๊ฒฝ๋กœ(graph[y][x] + 1)์„ ๋ฆฌํ„ดํ•˜๊ณ , ์ง€ํ›ˆ์ด๊ฐ€ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ๋ฅผ ๋ชจ๋‘ ํƒ์ƒ‰ํ–ˆ์Œ์—๋„ graph๋ฅผ ๋ฒ—์–ด๋‚˜์ง€ ๋ชปํ–ˆ๋‹ค๋ฉด ํƒˆ์ถœ์„ ๋ชปํ•œ๋‹ค๋Š” ์˜๋ฏธ์ด๋ฏ€๋กœ -1์„ returnํ•ฉ๋‹ˆ๋‹ค.

     

    ๐ŸŒฑ ์ •๋‹ต ์ฝ”๋“œ

    # !/usr/bin/env python
    # -*- coding: utf-8 -*-
    # boj 4179 ๋ถˆ!
    
    import sys
    from collections import deque
    
    input = sys.stdin.readline
    
    h, w = map(int, input().split())
    visited = [[False] * w for _ in range(h)]
    
    graph = []
    for _ in range(h):
        graph.append(list(input())[:w])
    
    fire_start = []
    for i in range(h):
        for j in range(w):
            if graph[i][j] == "J":
                jihoon_start = (i, j)
                graph[i][j] = 0
            elif graph[i][j] == "F":
                fire_start.append((i, j))
    
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    answer = 0
    
    
    def fire_bfs(start):
        global graph, w, h
        fire = deque([])
        visited = [[False] * w for _ in range(h)]
        for s in start:
            y, x = s
            fire.append((y, x))
            visited[y][x] = True
    
        while fire:
            y, x = fire.popleft()
    
            for i in range(4):
                ny, nx = y + dy[i], x + dx[i]
    
                if ny < 0 or nx < 0 or ny > h - 1 or nx > w - 1:
                    continue
                if visited[ny][nx] == False and graph[ny][nx] != "#":
                    graph[ny][nx] = graph[y][x] + "F"
                    visited[ny][nx] = True
                    fire.append((ny, nx))
    
    
    def jihoon_bfs(start):
        global graph, w, h
        y, x = start
        jihoon = deque([(y, x)])
        graph[y][x] = 0
        visited = [[False] * w for _ in range(h)]
        visited[y][x] = True
    
        while jihoon:
            y, x = jihoon.popleft()
    
            for i in range(4):
                ny, nx = y + dy[i], x + dx[i]
    
                if ny < 0 or nx < 0 or ny > h - 1 or nx > w - 1:
                    return graph[y][x] + 1
                if visited[ny][nx] == False and graph[ny][nx] != "#":
                    if graph[ny][nx] == "." or graph[ny][nx].count("F") - 1 > graph[y][x] + 1:
                        visited[ny][nx] = True
                        jihoon.append((ny, nx))
                        graph[ny][nx] = graph[y][x] + 1
        return -1
    
    
    fire_bfs(fire_start)
    answer = jihoon_bfs(jihoon_start)
    if answer > -1:
        print(answer)
    else:
        print("IMPOSSIBLE")
    ๋ฐ˜์‘ํ˜•

    ๋Œ“๊ธ€