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

2024. 9. 17. 00:42·coding test - python/Code Tree
728x90
반응형

 

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

 

삼멘 3일차

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

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

 

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

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

 


나의 풀이

  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 연산자 자주 쓰자!)

 

728x90
반응형

'coding test - python > Code Tree' 카테고리의 다른 글

삼성 SW역량테스트 기출 / 2019 상반기 오후 2번 문제 바이러스 백신 - BFS, 조합 / Python 파이썬  (8) 2024.09.19
삼성 SW역량테스트 기출 / 2018 상반기 오후 2번 문제 병원 거리 최소화하기 - 조합 / Python 파이썬  (4) 2024.09.19
삼성 SW역량테스트 기출 / 2017 하반기 오후 2번 문제 연산자 배치하기 - DFS / Python 파이썬  (0) 2024.09.14
삼성 SW역량테스트 기출 / 2017 하반기 오전 1번 문제 조삼모사 - 조합, 백트래킹 / Python 파이썬  (1) 2024.09.14
삼성 SW역량테스트 기출 / 2017 상반기 오전 2번 문제 외주 수익 최대화하기 - DP / Python 파이썬  (1) 2024.09.13
'coding test - python/Code Tree' 카테고리의 다른 글
  • 삼성 SW역량테스트 기출 / 2019 상반기 오후 2번 문제 바이러스 백신 - BFS, 조합 / Python 파이썬
  • 삼성 SW역량테스트 기출 / 2018 상반기 오후 2번 문제 병원 거리 최소화하기 - 조합 / Python 파이썬
  • 삼성 SW역량테스트 기출 / 2017 하반기 오후 2번 문제 연산자 배치하기 - DFS / Python 파이썬
  • 삼성 SW역량테스트 기출 / 2017 하반기 오전 1번 문제 조삼모사 - 조합, 백트래킹 / Python 파이썬
sillon
sillon
꾸준해지려고 합니다..
    반응형
  • sillon
    sillon coding
    sillon
  • 전체
    오늘
    어제
    • menu (614)
      • notice (2)
      • python (68)
        • 자료구조 & 알고리즘 (23)
        • 라이브러리 (19)
        • 기초 (8)
        • 자동화 (14)
        • 보안 (1)
      • coding test - python (301)
        • Programmers (166)
        • 백준 (76)
        • Code Tree (22)
        • 기본기 문제 (37)
      • coding test - C++ (5)
        • Programmers (4)
        • 백준 (1)
        • 기본기문제 (0)
      • 공부정리 (5)
        • 신호처리 시스템 (0)
        • Deep learnig & Machine lear.. (41)
        • Data Science (18)
        • Computer Vision (17)
        • NLP (40)
        • Dacon (2)
        • 모두를 위한 딥러닝 (강의 정리) (4)
        • 모두의 딥러닝 (교재 정리) (9)
        • 통계 (2)
      • HCI (23)
        • Haptics (7)
        • Graphics (11)
        • Arduino (4)
      • Project (21)
        • Web Project (1)
        • App Project (1)
        • Paper Project (1)
        • 캡스톤디자인2 (17)
        • etc (1)
      • OS (10)
        • Ubuntu (9)
        • Rasberry pi (1)
      • App & Web (9)
        • Android (7)
        • javascript (2)
      • C++ (5)
        • 기초 (5)
      • Cloud & SERVER (8)
        • Git (2)
        • Docker (1)
        • DB (4)
      • Paper (7)
        • NLP Paper review (6)
      • 데이터 분석 (0)
        • GIS (0)
      • daily (2)
        • 대학원 준비 (0)
      • 영어공부 (6)
        • job interview (2)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    programmers
    백준
    소수
    Python
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
sillon
삼성 SW역량테스트 기출 / 2018 하반기 오전 2번 문제 토스트 계란들 - BFS / Python 파이썬
상단으로

티스토리툴바