[10주차_화요일] 스도쿠 풀기

[yeahdy]

• 사이트 : 백준(BOJ)
• 문제: 스도쿠 풀기
• 번호: 2955
• 레벨: 골드2

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[Jewan1120]

🤔 시간복잡도 고려사항

• 구현 문제라 신경쓰지 않음

💡 풀이 아이디어

• 깡 구현 → 문제 지문대로 구현하면 되는 문제 (걍 스도쿠 풀 듯 풀면 됩니다)
• 타겟(숫자)가 들어갈 수 있는 자리가 한 곳이라면 그 자리에 타겟(숫자) 집어넣기
• 집어 넣을 자리가 없을 때까지 반복
• crossHatching(): 타겟이 들어갈 수 없는 자리 체크
• check(): 타겟이 적절한 위치에 들어갔을 때 해당 타겟을 기준으로 들어갈 수 없는 자리 체크
• isValid(): 타겟이 들어가야하는데 들어갈 수 없거나, 타겟이 중복돼서 들어가는지 유효성 체크 → ERROR를 출력
• putNumber(): 타겟이 들어갈 수 있는 자리가 1개인지 확인하고 1개라면 타겟 집어넣고 check()호출

  무슨 의도의 문제였을까요.. 백트래킹? 엇.. 문제 리뷰 남기니깐 골드 3됐어요..

[KodaHye]

🤔 시간복잡도 고려사항

• 스도쿠의 크기: 9 ⨉ 9
• 끝나는 조건이 명확하기 떄문에 엄청난 중첩된 반복문이 아닌 이상, 시간 초과 안날듯!!

💡 풀이 아이디어

변수

• boolean error: 스도쿠에 모순이 일어나는지 확인하는 변수
• int[][] map: 스도쿠를 표시할 이차원 배열
• boolean[][][] v: 1부터 9까지 위치할 수 있는 곳을 표시하는 변수
  • v[0][r][c] = true: 0은 map[r][c]에 올 수 없음
  • v[0][r][c] = false: 0은 map[r][c]에 올 수 있음
  • true가 마크 표시했다는 의미여서 true이면 올 수 없고, false(빈 공간)여야 올 수 있음
• HashSet<Integer>[] set: 원래 스도쿠를 3 X 3크기인 9개의 스토쿠 나누었을 때, 0 ~ 8번째 스도쿠마다 어떤 수가 있는지 저장하는 변수
  

풀이

• 9 ⨉ 9 스도쿠를 9개의 3 ⨉ 3 스도쿠라고 생각
  • 좌표가 r, c라면, 해당 좌표가 포함되는 (3 ⨉ 3)스도쿠의 idx:(r / 3) * 3 + c / 3
• 스도쿠에 숫자를 집어놓을 수 없을 때까지 반복
  1. 숫자 하나(k) 고르기 (1 ~ 9 for문으로 반복)
  2. 3 ⨉ 3 스도쿠를 0번에서 8번까지 탐색
     • k가 해당 3 ⨉ 3 스도쿠 안에 있다면, continue해서 다음 숫자 확인
     • k가 해당 3 ⨉ 3 스도쿠 안에 없다면, 어디에 들어갈 수 있는지 확인
     • 3 ⨉ 3 스도쿠를 확인하면서 k가 있을 수 있는 자리의 개수(canExistPoint) 찾기
     • k가 있을 수 있는 곳의 개수(canExistPoint)가 한 개라면 map에 표시해주기
       • v 배열에 표시해주기
       • set[스도쿠idx]에 k add 해주기

제가 난이도 다시 올려놨습니다

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 구현
• 스도쿠 크기 3 3 9

💡 풀이 아이디어

• 1~9 까지 타겟 숫자 크로스해칭

  • 타겟 숫자가 속한 가로줄 1차원 배열, 세로줄 1차원 배열, 3*3박스 배열 방문 체크
  • gridCheck[i / 3][j / 3] 같은 3*3 박스에 포함되어 있다면 같은 인덱스(i,j)가 되므로 방문 유무 확인 가능

• 스도쿠 배열 순회하기

  • 3 3 박스 각 왼쪽 꼭지점을 시작으로 3 3 박스 별로 순회

• 타겟 숫자가 들어갈 수 있는 서브그리드 찾기

  • 가로줄 1차원 배열, 세로줄 1차원 배열 이 방문 처리되어 있지 않아야 함
  • 스도쿠 판이 비어있고(0) 단 1칸만 존재해야함
  • 만약 여러 자리가 있거나 자리를 찾지 못했다면 해당 스도쿠는 문제가 있기 때문에 ERROR

서브그리드에서 자리를 찾은 후에 이곳의 가로줄,세로줄,3*3배열 방문 처리 하는걸 놓쳤어요.. 그리고 숫자를 다 찾을 때까지 무한 반복을 돌릴때 flag 를 true 로 만드는 시점에서 많이 헤맸네요 ㅜㅜ.. 🤦‍♀️🤦‍♀️🤦‍♀️🤦‍♀️🤦‍♀️🤦‍♀️🤦‍♀️🤦‍♀️🤦‍♀️🤦‍♀️🤦‍♀️🤦‍♀️🤦‍♀️🤦‍♀️

[icegosimperson]

🤔 시간복잡도 고려사항

• 입력 : 9줄, 1~9 + '.' -> 구현

💡 풀이 아이디어

• solve(): 1~9까지 CrossHatching() 구현
• CrossHatching() : 배치하려는 좌표와의 중복 검사
  • row[i], col[j], square[i/3][j/3]에 존재 -> error = true -> return false
  • error : 풀이 가능 여부 판단 변수
  • 배치 가능할 경우 : return true -> 재귀호출
• check() : 3x3 네모안에 해당 칸에 숫자를 배치할 수 있는지 확인
  • 숫자 배치 자리x : return false
  • 배치 가능 : row, col 갱신

    제약조건 유지하도록 구현하는게 어려웠습니다. 구현 문제 연습 많이 많이..👊🏻🥋👊🏻

[yeongleej]

🤔 시간복잡도 고려사항

• 9 * 9

=> 스도쿠 조건이 있기 때문에 완전탐색 가능

💡 풀이 아이디어

• 유효성 검사

  • fillArea(n): 숫자 n이 들어갈 곳이 있는지 유효성 검사 => fillLine(n) : n의 십자가 방문처리 => fillSquare(n) : n이 포함된 3*3박스 방문처리
  • 방문처리 후, n이 들어갈 수 있는 공간이 있는지 체크 => checkLiine(n) : n의 십자가에 동일한 숫자가 있는지 체크 => checkSquare(n) : n의 3*3박스에 동일한 숫자가 있거나 or 들어갈 자리가 있는지 체크

• CrossHatching

  • 유효성 검사와 같이 fillArea()를 진행 후, CrossHatcing에 적합한 곳 찾아서 진행
  • 더이상 들어갈 숫자들이 없다면 루프 종료

입력에 제시된 숫자로만 스도쿠를 풀어서,,,, 계속 틀렸네요,,,, ㅎㅎㅎㅎ 휴우~ 스도쿠 개념 공부나 해야겠어요 ^^

[baexxbin]

🤔 시간복잡도 고려사항

• 9 * 9
• 완전탐색 가능

💡 풀이 아이디어

• int[][] row, col, box: 가로, 세로, 3 * 3박스 각 위치에 숫자 들어있는지 체크

  아니,, 왜 지금 생각하니까 2차원으로 했을까요 굳이 3개다...? 원래 1차원이였는데 이것부터가 문제인가...

• 입력 받을때 유효성 검사 (입력이 잘못되었다면 에러 반환)
• 숫자가 업데이트 될 동안 스도쿠 진행
  • 이때 doTry변수로 검사해서 아예 시도 조차 못할 경우는 에러처리
• crossHatching()
  • 가로, 세로, 3 * 3에 각각 놓을 수 있는지 확인
  • 보드가 0이고 가로 세로 박스가 다 들어갈 수 있을때 cnt++
  • cnt가 1일때만 자리 업데이트 하기

    이 부분도 의심가는 부분이긴한데 중복이 생기려나요,,,,? 하지만 자리가 있다면 바로 확정해서 다음 조건을 확인할때 겹치진 않을거같은데 가로세로박스 모두 확인한 다음에 넣어줘야하는걸까요...?

ㅠㅠ풀지 못했습니다ㅠㅠ 머리가 안돌아가요,, 풀진못했지만 말썽꾸러기가되면 안되니까,,,, 일단 이슈는 작성했습니다ㅜㅜ 좀 이따 리뷰를 열심히 들어보겠습니다,,ㅠ,ㅠ