developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 삼성코테자바풀이
  • c++ 빌더 패턴
  • 삼성코테구현문제추천
  • MA모형
  • 카카오코테java풀이
  • SW역량테스트파이썬
  • 삼성코테파이썬풀이
  • 시계열
  • 백준파이썬풀이
  • 통계분석
  • 카카오코테
  • SW역량테스트파이썬풀이
  • 삼성코테기출
  • AR모형
  • 코테파이썬
  • 데이터분석
  • 삼성코테자바꿀팁
  • Arima
  • 삼성코테기출자바풀이
  • 삼성코테자바준비
  • 운영체제인터럽트
  • 삼성코테파이썬준비
  • c++디자인패턴
  • 삼성코테준비
  • 통계학
  • 삼성코테파이썬
  • 시계열분석
  • ARIMA모형
  • BOJ파이썬풀이
  • 삼성코테구현풀이

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

SW Expert Academy - 디저트카페 (python)

2021. 10. 22. 20:58

❓ 문제 - SW Expert Academy 디저트카페  python 풀이법

 

출처 

(https://swexpertacademy.com/main/solvingProblem/solvingProblem.do)

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

다른 분의 코드 참조하여 해결하였습니다...

(https://dongsik93.github.io/algorithm/2019/07/04/algorithm-swexpert-sw2105/)

 

SW expert 2105 디저트 카페문제-python - 동식이 블로그

2105 디저트 카페

dongsik93.github.io

 

 

📝 문제해결법

1. 이 문제는 완전탐색(DFS)+구현로 풀었다.

  • 문제에서 모든 행과 열을 돌면서 사각형(오른쪽아래-왼쪽아래,왼쪽위,오른쪽 위 순서로)을 그릴 수 있는지 DFS로 검사한다.
  • 우선 문제에서 주어진 조건에서 사각형을 그린 후 마지막으로 처음시작점에 다시 돌아와야 하므로 시작점 sx, sy를 전역 변수로 선언한다.
  • 또한 문제에서 주어진 조건에서 사각형을 그릴 때, 디저트 카페의 종류가 중복되면 안되기 때문에 사각형을 그릴 때마다 리스트에 해당 디저트 종류의 수를 넣어준다. DFS로 사각형을 다 그린 후, 다시 리스트에 디저트 종류의 수를 빼준다.
  • DFS를 돌릴 때, 사각형을 완성한 기준은 그전에 이동한 방향(d)가 3(오른쪽 위)이고, 이동한 위치가 시작점과 같으면 해당 사각형에 들어간 카페의 수의 최대값을 갱신한다.
  • 만약 그전에 이동 방향에 따라 이동한 위치가 격자칸 범위에 벗어나면 사각형을 그리지 못하므로 리턴한다.
  • 만약 그전에 이동 방향에 따라 이동한 위치가 이미 디저트의 수에 중복되는 곳이라면 사각형을 그리지 못하므로 리턴한다.
  • 그 후에는 사각형을 그리기 위해 이동처리 해야하므로 방문 리스트에 이동한 카페의 디저트 수를 넣어주고, 이전 이동 방향을 기준으로 0, 1(오른쪽 아래, 왼쪽 위) 이면 자신의 방향을 유지한채 이동 시키거나, 방향 +1 해준 상태로 사각형을 그리기 위해 DFS를 호출한다.
  • 만약 이전 이동한 방향이 2(왼쪽 위)이면 만약 시작 위치와 행,열이 반대일 땐 사각형을 그리기 위해서 무조건 방향을 +1해주고 이동시켜 사각형을 그리고, 아직 시작위치와 행,열이 반대가 아니라면 2방향으로 한칸 더 이동처리 하여 사각형을 그린다.
  • 만약 이전 이동한 방향이 3(오른쪽 위)라면 해당 방향을 유지한채 이동해서 사각형을 그릴 수 있으므로 DFS를 호출한다.

2. 문제 풀면서 느낀점

  • 처음 기본 DFS 방식만으로 사각형을 그리려고 했다가 실패하였다... 사각형을 구현하는 방법을 꼭 기억해두자..^^

 

💻 소스코드

T = int(input())
dx = [1, 1, -1, -1]
dy = [1, -1, -1, 1]

def dfs(num, x, y, d):
    global max_cafe
    global sx, sy
    if d == 3 and x == sx and y == sy:
        max_cafe = max(max_cafe, num)
        return
    elif not (0<=x<n and 0<=y<n):
        return
    elif board[x][y] in visited:
        return
    else:
        visited.append(board[x][y])
        if d in [0, 1]:
            dfs(num+1, x+dx[d], y+dy[d], d)
            dfs(num+1, x+dx[d+1], y+dy[d+1], d+1)
        elif d == 2:
            if x + y != sx + sy:
                dfs(num+1, x+dx[2], y+dy[2], 2)
            else:
                dfs(num+1, x+dx[3], y+dy[3], 3)
        else:
            dfs(num+1, x+dx[3], y+dy[3], 3)
        visited.remove(board[x][y])
    return


for test_case in range(1, T+1):
    n = int(input())
    board = [list(map(int, input().split())) for _ in range(n)]
    max_cafe = -1
    visited = []
    for i in range(n):
        for j in range(n-1):
            sx, sy = i, j
            visited.append(board[i][j])
            dfs(1, i+1, j+1, 0)
            visited.remove(board[i][j])

    print(f'#{test_case} {max_cafe}')

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

SW Expert Academy - 벌꿀 채취 (python)  (0) 2021.10.23
SW Expert Academy - 보호 필름 (python)  (0) 2021.10.23
SW Expert Academy - 수영장 (python)  (0) 2021.10.22
SW Expert Academy - 줄기세포배양 (python)  (0) 2021.10.22
BOJ - 마법사 상어와 비바라기 21610번 (python)  (0) 2021.10.21
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • SW Expert Academy - 벌꿀 채취 (python)
    • SW Expert Academy - 보호 필름 (python)
    • SW Expert Academy - 수영장 (python)
    • SW Expert Academy - 줄기세포배양 (python)
    developer-ellen
    developer-ellen

    티스토리툴바