KOREATECH 1043: 위성 사진

Link : judge.koreatech.ac.kr/problem.php?id=1043

---

Python

from sys import stdin
 
map_x, map_y = list(map(int, stdin.readline().strip().split()))
 
map_data = [[s for s in stdin.readline().strip()] for i in range(map_y)]
 
 
def able_move(x, y):
    if x < 0 or y < 0:
        return False
    if x >= map_x or y >= map_y:
        return False
    if map_data[y][x] == '*':
        return True
    else:
        return False
 
 
def BFS(p_x, p_y):
    que = set()
    que.add((p_x, p_y))
    counter = 0
    while len(que):
        t_x, t_y = que.pop()
        map_data[t_y][t_x] = '.'
        counter += 1
        if able_move(t_x + 1, t_y):
            que.add((t_x + 1, t_y))  # right
        if able_move(t_x - 1, t_y):
            que.add((t_x - 1, t_y))  # left
        if able_move(t_x, t_y + 1):
            que.add((t_x, t_y + 1))  # down
        if able_move(t_x, t_y - 1):
            que.add((t_x, t_y - 1))  # up
    return counter
 
 
data = []
for i in range(map_y):
    for j in range(map_x):
        if able_move(j, i):
            data.append(BFS(j, i))
 
if len(data) > 0:
    print(max(data))
else:
    print(0)
 

FeedBack

1. BFS정석은 FIFO의 자료구조인 pop, popleft, append가 O(1)에 해결되는 deque 등 queue를 이용하는게 좋습니다.
   하지만 저는 편의를 위해 중복이 허용되지 않는 set을 이용하였습니다.

---

 

 

 

cjw.git@gmail.com