Egomi Space

https://www.acmicpc.net/problem/2580소요시간: 3시간 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ 삼성 가고파요 제발풀이입니다 참고만 해주세요 알고리즘 초보자입니다.colMaps[i][j] ====> i행에 j라는 숫자가 있다면 1, 없다면 0rowMaps[i][j] ====> i열에 j라는 숫자가 있다면 1, 없다면 0groupMaps[i][j] ====> i그룹에에 j라는 숫자가 있다면 1, 없다면 0 (그룹의 인덱스의 경우 i = 3*(x좌표/3) + y좌표/3 으로 표현해 줬다.) N-Queen 문제와 마찬가지로, 다음 노드 방문 여부를 판단(isPromising)해야 한다.(백트레킹)그런데, 모든 행, 열, 그룹을 탐색하기에는 시간이 너무 오래 걸린다.그래서 공통된 행..

A B C D 를 선택할 수 있는 경우의 수를 구할 때, 0000 0001 0010 0011 0100 ... 식으로 0000에 1씩 더해주면 구할 수 있다.따라서 총 선택 갯수는 2^4(아무것도 선택하지 않는 경우 포함) 이다.그리고 경우를 선택한 경우 각 bit가 0인지 1인지 판단하기 위하여 0001을 left로 1bit씩 4번 shift 해준 후 & 연산을 해준다.(비트마스크 사용)예를 들어, 0011 의 경우 각 bit가 0인지 1인지 판단하기 위하여0011 & 0001 -> 0001 (1)0011 & 0010 -> 0010 (2)0011 & 0100 -> 0000 (0)0011 & 1000 -> 0000 (0)으로 결과가 0이 아닐 경우, ON(1)임을 판단할 수 있다.12345678910111..

백트레킹이란? 특정 노드의 유망성(Promising)을 검사하고 유망하다면 자식 노드로, 유망하지 않다면 그 다음 부모 노드로 탐색을 하는 것이다.N-Queen은 N*N개의 체스판에서 N개의 Queen이 서로 열, 행, 대각으로 겹치지 않는 경우의 수를 구하는 것이다. 첫 번째 부모(첫 번째 행)는 1~n까지의 열을 가질 수 있고두 번째 부모(두 번째 행)은 1~n까지의 열을 가질 수 있고 -> point세 번째 부모(세 번째 행)은 1~n까지의 열을 가질 수 있고...N 번째 부모(N번째 행)은 1~n까지의 열을 가질 수 있다.즉 ,배열로 이용하면a0 a1 a2 .......... an-1 -> 열 [0] [1] [2] .............[n-1] -> 행로 표현할 수 있다.(1차원 배열로 나타낼..

Maps를 무작정 조작하려 들기보다는, 출력에 필요한 정보를 dfs로 전달하는 것이 좋다.아래처럼, DFS에 들어갔을 때 -> 현재 상태에 대한 배열을 만들고 -> 함수 인자 값으로 받아온 이전 상태로 현재 상태에 대한 배열을 채워준다. -> 그리고 채워준 현재 상태의 배열로 DFS에 들어간다.굳이 인자에 들어온 값을 조작하려 들지 말고, 인자로 들어온 이전 값을 활용하여 현재 값을 채운 후 보내주자. 그러면 이것이 백트래킹이 된다. 또한, 삼항 연산자를 쓰니 굉장히 보기 편하다. 반성해야겠다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.