알고리즘/프로그래머스

[프로그래머스] N-Queen

2021. 1. 27. 21:14
728x90
반응형
 

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한 사항

-퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.

-n은 12이하의 자연수 입니다.

입출력 예

n

result

4

2

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

접근법

하나의 배열 col을 생성한 뒤, 하나씩 채워갑니다. col[0]은 0번째에 Q가 있는 인덱스, col[1]은 1번째에 Q가 있는 인덱스를 뜻합니다. nqueen부분에서는 col의 n번째에 각각 인덱스를 하나씩 채워주는 역할을 합니다. 이때 check에서 검사를 한 뒤, 그 자리에 올수 있다면 n+1자리를 검색해 봅니다. 이렇게 계속 하다보면, col의 길이와 n이 같아지는 시점에 count를 더해주면 됩니다.(n이 col의 길이만큼 왔다는 것은, check를 모두 통과했기 때문입니다.)

​

나의 코드

count = 0
def check(col,n):
    for i in range(n):
        if (col[n] in col[:n]) or (abs(col[n]-col[i]) == abs(n-i)): return False
    return True

def nqueen(col,n):
    global count
    if len(col) == n: 
        count += 1
    else:
        for i in range(len(col)):
            col[n] = i
            if check(col,n):
                nqueen(col,n+1)

def solution(n):
    col = [0]*n
    nqueen(col,0)
    return count
반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

[프로그래머스] 불량 사용자  (0) 2021.01.28
[프로그래머스] 배달  (0) 2021.01.27
[프로그래머스] 섬 연결하기  (0) 2021.01.27
[프로그래머스] N으로 표현  (0) 2021.01.27
[프로그래머스] 단속카메라  (0) 2021.01.27
'알고리즘/프로그래머스' 카테고리의 다른 글
  • [프로그래머스] 불량 사용자
  • [프로그래머스] 배달
  • [프로그래머스] 섬 연결하기
  • [프로그래머스] N으로 표현
컴공누나
컴공누나
ML 엔지니어 컴공누나입니다:) wodbs9522@gmail.com
컴공누나의 지식 보관소ML 엔지니어 컴공누나입니다:) wodbs9522@gmail.com
컴공누나
컴공누나의 지식 보관소
컴공누나
전체
오늘
어제
  • 분류 전체보기 (267)
    • 컴공누나 소개 (2)
    • 언어 마스터 (4)
      • 파이썬 (4)
    • 알고리즘 (159)
      • 프로그래머스 (120)
      • 백준알고리즘 (39)
      • 알고리즘기초 (0)
    • 인공지능공부 (62)
      • 인공지능기본지식 (6)
      • LLM (3)
      • 인공지능기초수학 (9)
      • 프레임워크 (2)
      • 자연어처리 (16)
      • 컴퓨터비전 (2)
      • 그래프 (24)
      • Prolog (0)
    • 다른 분야 (4)
      • Docker (1)
      • Web (3)
    • 논문 (10)
      • 논문리딩 (6)
      • 게제논문 (4)
    • 꿀팁 (19)
      • 오류 정리 (8)
      • 소소한 팁 (11)

블로그 메뉴

  • 홈
  • 태그
  • 글쓰기
  • 관리

공지사항

인기 글

태그

  • GPT
  • transformer
  • GNN
  • stanfordgnn
  • 선형대수
  • 백준
  • 스탠포드그래프
  • 그래프강의
  • selfattention
  • Bert
  • 그래프
  • stanfordgraph
  • 그래프신경망
  • 파이썬
  • 프로그래머스
  • nlp
  • cs224w
  • 영상기반상식추론
  • 선형대수기초
  • 자연어처리

최근 댓글

최근 글

글쓰기 / 관리자
hELLO · Designed By 정상우.
컴공누나
[프로그래머스] N-Queen
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.