삼성 SW역량테스트 기출 / 2018 하반기 오전 2번 문제 토스트 계란들 - BFS / Python 파이썬

 

*문제 출처는 삼성전자, 코드트리에 있습니다.

 

삼멘 3일차

문제 제목: 토스트 계란들 - BFS

문제 사이트: https://www.codetree.ai/training-field/frequent-problems/problems/toast-eggmold/description?page=1&pageSize=20&tier=11%2C11

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

---

나의 풀이

1. 입력 받기:
   • 격자의 크기 n, 계란 차이 범위 L과 R을 입력받는다.
   • 격자에서 각 칸의 계란 수를 입력받아 maps에 저장한다.
2. BFS 함수 정의:
   • 주어진 시작 위치에서 BFS를 실행하여 계란 차이가 L 이상 R 이하인 인접 칸을 탐색한다.
   • 탐색한 칸의 계란을 평균으로 업데이트한다.
   • BFS가 실행된 후 계란 변화 여부를 반환한다.
3. 주 반복문:
   • 모든 칸을 순회하면서 방문하지 않은 칸에서 BFS를 수행한다.
   • BFS 후에 계란이 변화한 경우 state를 True로 설정하고, 이동 횟수를 증가시킨다.
   • 계란 변화가 없는 경우 반복을 종료한다.
4. 결과 출력:
   • 계란 이동 횟수를 출력한다.

 

 

 

나의 풀이

from collections import deque

n, L, R = map(int, input().split())

maps = [list(map(int, input().split())) for _ in range(n)]
answer = 0

def BFS(start, visited):
    queue = deque(start)
    sum_ = []
    while queue:
        q = queue.popleft()
        qx, qy = q[0], q[1]
        
        direct = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        for i in range(4):
            xx = qx + direct[i][0]
            yy = qy + direct[i][1]

            if 0 <= xx < n and 0 <= yy < n and not visited[xx][yy]:
                if L <= abs(maps[qx][qy] - maps[xx][yy]) <= R:
                    queue.append([xx, yy])
                    visited[xx][yy] = True
                    sum_.append([xx, yy])

    if len(sum_) > 1:
        value = sum(maps[i[0]][i[1]] for i in sum_) // len(sum_)
        for i in sum_:
            maps[i[0]][i[1]] = value
        return visited, True
    else:
        return visited, False

while True:
    state = False
    visited = [[False] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                visited, state_ = BFS([[i, j]], visited)
                state = state or state_ ## 둘 중 True가 있으면 True 반환
                
    if not state:
        break

    answer += 1

print(answer)

 

 

 

2차원 배열의 깊은 복사와 얕은 복사 설명:

1. 얕은 복사 (Shallow Copy):
   • 정의: 배열의 구조만 복사하고, 내부 객체(리스트 등)에 대한 참조만 복사함.
   • 결과: 복사된 배열과 원본 배열이 같은 내부 객체를 참조하므로, 내부 객체의 변경이 원본 배열에도 영향을 미침.
2. 깊은 복사 (Deep Copy):
   • 정의: 배열의 구조와 내부 객체 모두를 새로 복사함.
   • 결과: 복사된 배열과 원본 배열이 서로 독립적이므로, 하나의 배열에서 변경을 해도 다른 배열에는 영향을 미치지 않음.

예제 코드와 설명:

# 원본 2차원 배열 

maps = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]

 

 

얕은 복사 예제:

shallow_copy = maps  # 얕은 복사
shallow_copy[0][0] = 10
# 결과: shallow_copy와 maps 모두 [10, 2, 3]으로 변경됨

 

깊은 복사 예제:

 

import copy
deep_copy = copy.deepcopy(maps)  # 깊은 복사
deep_copy[0][0] = 10
# 결과: deep_copy는 [10, 2, 3]으로 변경되지만, maps는 여전히 [1, 2, 3]으로 남음

• 얕은 복사:
  • shallow_copy는 maps와 같은 객체를 참조함.
  • 내부의 값이 변경되면 maps에도 영향을 미침. 
    shallow_copy = maps
  •  
• 깊은 복사:
  • deep_copy는 maps의 모든 값과 구조를 새로 복사함.
  • deep_copy의 변경은 maps에 영향을 미치지 않음.
     
    deep_copy = copy.deepcopy(maps)

 

---

※ 알아야 할 것

- 2차원 배열을 그냥 .copy() 하면 얕은 복사가 되므로, 깊은 복사를 할거면 [[maps[i][j] for j in range(n)] for i in range(n)] 이런식으로 배열 복사를 진행해야 주소값까지 복사되지않음

- copy.deepcopy() 매소드도 있었는데 그냥 한줄코딩으로 하는게 나은듯

- state = state or state_ (둘중 하나가 참이면 참을 출력하는 or 연산자 자주 쓰자!)