[Swift/Python] 백준_음식물 피하기(1743)

문제

 

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

1743번: 음식물 피하기

 

 

풀이

 

미리 이차원배열을 전부 0으로 초기화하고 입력받은 쓰레기 위치를 1로 바꿔준 뒤, BFS를 이용해 가장 많은 쓰레기가 붙어있는 영역을 구해주면됨.

 

Swift

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = input[0]; let m = input[1]; let k = input[2]
var result = 0
let dx = [1,0,-1,0]; let dy = [0,1,0,-1]
var trash: [[Int]] = []
for _ in 0..<k {
    trash.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}
var board = Array(repeating: Array(repeating: 0, count: m), count: n)
for point in trash {
    board[point[0] - 1][point[1] - 1] = 1
}
for i in 0..<n {
    for j in 0..<m {
        if board[i][j] == 1 {
            var temp = 1
            board[i][j] = 0
            var queue = [(i,j)]
            while !queue.isEmpty {
                let cur = queue.removeFirst()
                for k in 0..<dx.count {
                    let newX = cur.0 + dx[k]
                    let newY = cur.1 + dy[k]
                    if newX < 0 || newY < 0 || newX >= n || newY >= m {
                        continue
                    }
                    if board[newX][newY] == 1 {
                        queue.append((newX,newY))
                        board[newX][newY] = 0
                        temp += 1
                    }
                }
            }
            result = max(result,temp)
        }
    }
}
print(result)

 

Python

import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
board = [[0 for _ in range(m)] for _ in range(n)]
dx = [1,0,-1,0]; dy = [0,1,0,-1]
result = 0
for _ in range(k):
    temp = list(map(int,input().split()))
    board[temp[0] - 1][temp[1] - 1] = 1
for i in range(n):
    for j in range(m):
        if board[i][j] == 1:
            count = 1
            board[i][j] = 0
            queue = [(i,j)]
            while queue:
                cur = queue.pop(0)
                for k in range(len(dx)):
                    newX = cur[0] + dx[k]
                    newY = cur[1] + dy[k]
                    if newX < 0 or newY < 0 or newX >= n or newY >= m:
                        continue
                    if board[newX][newY] == 1:
                        count += 1
                        board[newX][newY] = 0
                        queue.append((newX,newY))
            result = max(result,count)
print(result)

 

 

_____________________________________________________________________________________________________

 

스위프트가 익숙해서 훨씬 편하긴하지만 익숙해진다면 파이썬이 더 쉬울 것 같은..