[백준/Python] 2589번(그래프, 브루트포스 ,BFS)_보물섬

📌문제 유형

그래프, 브루트포스, BFS (골드5)

 

📌문제

2589번: 보물섬

 

📌나의 문제풀이

import copy # 깊은 복사 
from collections import deque

a,b = map(int,input().split())

maps = []
visited = []
for _ in range(a):
    tmp = input()
    tmp = tmp.replace('W','0')
    tmp = tmp.replace('L','1')
    tmp = list(map(int,tmp))
    maps.append(tmp)
    visited.append(tmp)

ans = 0
for x in range(a):
    for y in range(b):
        
        q = deque()
        if maps[x][y] == 1:
            result = 0
            visited = copy.deepcopy(maps)
            q.append([x,y])
            visited[x][y] = 0
            cnt = 0

            while q:
                x_,y_ = q.popleft()

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

                for i in range(4):
                    nx = x_ + dx[i]
                    ny = y_ + dy[i]
                    if 0 <= nx < a and 0 <= ny < b and visited[nx][ny] == 1:
                        visited[nx][ny] = visited[x_][y_] + 1
                        cnt = max(cnt,visited[nx][ny])
                        q.append([nx,ny])

            if ans < cnt:
                ans = cnt

print(ans)

# 보물섬
# https://www.acmicpc.net/problem/2589

import copy # 깊은 복사 
from collections import deque

a,b = map(int,input().split())

maps = []
visited = []
for _ in range(a):
    tmp = input()
    tmp = tmp.replace('W','0')
    tmp = tmp.replace('L','1')
    tmp = list(map(int,tmp))
    maps.append(tmp)
    visited.append(tmp)

ans = 0
for x in range(a):
    for y in range(b):
        
        q = deque()
        if maps[x][y] == 1:
            result = 0
            visited = copy.deepcopy(maps)
            q.append([x,y])
            visited[x][y] = 0
            cnt = 0

            while q:
                x_,y_ = q.popleft()

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

                for i in range(4):
                    nx = x_ + dx[i]
                    ny = y_ + dy[i]
                    if 0 <= nx < a and 0 <= ny < b and visited[nx][ny] == 1:
                        visited[nx][ny] = visited[x_][y_] + 1
                        q.append([nx,ny])

            if ans < max(map(max,visited)):
                ans = max(map(max,visited))

print(ans)

 

📌 다른사람의 문제풀이

from collections import deque

n,m=map(int, input().split())
maps=[]
for i in range(n):
  maps.append(list(input()))

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

def bfs(i,j):
  queue=deque()
  queue.append((i,j))
  visited=[[0]*m for _ in range(n)]
  visited[i][j]=1
  cnt=0
  while queue:
    x,y=queue.popleft()
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if nx<0 or nx>=n or ny<0 or ny>=m:
        continue
      elif maps[nx][ny]=='L' and visited[nx][ny]==0:
        visited[nx][ny]=visited[x][y]+1
        cnt=max(cnt,visited[nx][ny])
        queue.append((nx,ny))
  return cnt-1

result=0
for i in range(n):
  for j in range(m):
    if maps[i][j]=='L':
      result=max(result,bfs(i,j))

print(result)

 

📌 리뷰 

- 방문노드 안 만드려고, copy.deepcopy() 이용해서 visited 값 초기화 후 더함

12. 얕은 복사(shallow copy)와 깊은 복사(deep copy)

- [이것만 고치면 코드 쉽게 맞혔을 것...]
이차원 배열에서 최댓값 찾으려고 max(max(vistied) 사용했는데, 첫번째 원소의 값이 가장 작은 원소가 나온다...!

• 이차원 배열 최댓값 찾는 방법 : max(map(max,vistied))

Python 2차원 배열의 최대값, 최소값 찾기